Priority Queue using Doubly Linked List

Last Updated on December 13, 2022 by Prepbytes

Introduction

We have seen so many data types but in the below article we are going to learn about the abstract data type similar to a regular queue or stack in which each element is included with a priority of its own. Now, lets just look into the program for priority queue using doubly linked list

Problem Statement for priority queue using doubly linked list

In this problem, we are given a set of nodes with their respective priority and our task is to implement a priority queue using a doubly linked list, which supports the following operations:

Operations

push(x, p): This function inserts an element x with priority p in the priority queue at the appropriate position.
pop(): This function removes and returns the element with the highest priority in the priority queue.
peek(): This function returns the element with the highest priority in the priority queue without removing it.

Now what we are going to do is, create a doubly linked list, but with a few tweaks such that the highest priority element will always be the head of the linked list. That means the list will be sorted in the descending order of the elements based on their priority. By doing this, we can do the peek() operation in O(1) time.

For the push() operation, we have to find a suitable position based upon the priority to insert the current node in the linked list so that the overall order of the priority queue is maintained. This will take O(n) time. Let us have a look at the approaches.

Now, let’s implement these functions one by one.

push(x, p)

In push(x,p) operation to push an elemet x with priority p, we will have to first search for an appropriate position in the priority queue and then insert the element at that position.

The appropriate place to insert is just before the first element whose priority is less than p i.e. the priority of element we are inserting currently in push operation.

For example
If the priorityQueue:

Note: The first element inside brackets represents the data, and the second element represents priority.

• If we want to push(6, 3), the appropriate place for (6,3) is just before (2,2).

Therefore, the priorityQueue after insertion is:

Algorithm for priority queue using doubly linked list

• We will traverse the priority queue starting from the head node and find the first node whose priority is less than p.
• One of the 3 cases is possible.
  1. There is no element whose priority is less than p. In this case, the new node will be inserted at the end of the priority queue.
  2. All the nodes have priority queue less than p. In this case, the new node will be inserted at the beginning of the priority queue.
  3. There are some nodes which have priority greater than p and some which have priority less than p. In this case, the new node will be inserted before the first node with priority less than p. This case is explained in the above example.

Dry Run for priority queue using doubly linked list

Code Implementation for priority queue using doubly linked list

//Implementing push function
void push(int data, int priority) {
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    Node *node = new Node(data, priority);
   
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1     
if (parent == NULL) {
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 
    else if (temp == NULL) {
        parent->next = node;
        node -> prev = parent;
    }
    else {
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}

Time Complexity: O(n), as we need to make traversal to find the first node having priority less than the priority of the node which we are pushing.

pop()

The element with the highest priority will always be present at the beginning of the priority queue.

• If the priority queue is not empty, we will delete the first element and return it, else it is impossible to pop.
• Else do nothing and return -1.

Dry Run for priority queue using doubly linked list

Code Implementation for priority queue using doubly linked list

int pop() {
    
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    return -1;
}

Time Complexity: O(1), as the element which we are seeking is at the head of the priority queue, and we have a pointer to head.

peek()

The element with the highest priority will always be present at the beginning of the priority queue.

• If the priority queue is not empty, we will have to return the first element of the priority queue as it is the element with the highest priority.
• Else return -1.

Dry Run for priority queue using doubly linked list

Code Implementation for priority queue using doubly linked list

int peek() {
    
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

Time Complexity: O(1), as the element which we are seeking is at the head of the priority queue, and we have a pointer to head.

Code Implementation:

#include 
using namespace std;

class Node {
    public:
    int data, priority;
    Node *next;
    Node *prev;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = prev = NULL;
    }
};

Node *head = NULL;
void push(int data, int priority) {
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    Node *node = new Node(data, priority);
   
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1     
if (parent == NULL) {
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 
    else if (temp == NULL) {
        parent->next = node;
        node -> prev = parent;
    }
    else {
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}
int peek() {
    
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int pop() {
    
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    return -1;
}
int main() {
    push(5, 2);
    push(1, 3);
    cout<

						 

Output

1
7
1
5

Time Complexity: O(N) for push operation, O(1) for pop operation, and O(1) for peek operation.
Space Complexity: O(N), where N is the total number of nodes.

Conclusion

So, in the above article we can understand how the priority queue is similar yet different from the regular queue or stack as in this kind of queue, every element it contains is generally associated with a priority. This is an important coding interview question. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs

1. Which function is used in the priority queue?


The push() function is used to insert an element in the collection of priority queues.


2. What is a real time example for priority queue?


We can take an example of a police station, where the people come to register their complaints. The complaints get registered in the order of the complexity in the issue.


3. What is peek() in a Queue?


A peek() is used to fetch the first value or the value which is present in the head of the queue.