Types of Priority Queue in Data Structure?

Introduction

A queue is a data structure that follows the concept of FIFO(First in, First out). It means an element that is inserted first into the queue will be taken out first only. The same pattern applies to all the elements in a queue. For example, the line person standing in a movie theatre to get a movie ticket represents a queue. The person standing in front will get the ticket first.

Priority Queue

It is an extension of the queue that works in a normal manner. The difference is in a queue the elements follow FIFO order but in priority queue, every element has a priority based on which it is taken in operation.

At the time of insertion operation, it follows the same concept of queue and then priority queue moves the higher prioritised element in the beginning followed by lower prioritised ones.

Priority queue allows insertion only for the elements that are comparable and hence it sorts the elements in the queue either in ascending or descending order. An example of a priority queue is a higher critical patient being served in a hospital first to the ones having normal cough and fever.

Characteristics of Priority Queue

The following are the characteristics of priority queue -

1. Every element possesses some priority level.
2. An element with the highest priority is moved to the front and deleted first.
3. If two elements have the same priority level, then it follows the idea of a normal queue, that is, FIFO.

Types of Priority Queue

There are two types of priority queue are as follows -

Ascending order priority queue - In an ascending order priority queue, the highest priority is given to the smallest number in the queue.

For example, 4, 8, 2, 6, 10 numbers when converted to a priority queue form - 2, 4, 6, 8, 10.

Descending order priority queue - In descending order priority queue, the highest priority element is given to the largest element in the queue.

For example, 4, 8, 2, 6, 10 numbers when converted to a priority queue form - 10, 8, 6, 4, 2.

How is The Priority Queue Implemented in Data Structures?

How is the priority queue implemented in data structures?

1. Linked list - In a linked list the higher priority element is represented at the head of the linked list and based on that priority other elements are allocated in the linked list. Thus, removing the highest priority element takes constant time complexity O(1).

If insertion operation is being performed in the priority queue, all the elements are traversed in order to find the correct priority of the inserting element. Hence, the push operation takes O(N) time.

Algorithm Steps

PUSH(HEAD, DATA, PRIORITY)

Step 1: Create new node with the value as DATA and PRIORITY

Step 2: Check if HEAD has a lower priority level. If true, follow Steps 3-4 and end. Else goto Step 5.

Step 3: NEW -> NEXT = HEAD

Step 4: HEAD = NEW

Step 5: Set TEMP to head of the list

Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY

Step 7: TEMP = TEMP -> NEXT

[END OF LOOP]

Step 8: NEW -> NEXT = TEMP -> NEXT

Step 9: TEMP -> NEXT = NEW

Step 10: End

POP(HEAD)

Step 1: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.

Step 2: Free the node at the head of the list

Step 3: End

PEEK(HEAD):

Step 1: Return HEAD -> DATA

Step 2: End

C++ Code:

<code>

#include <bits/stdc++.h>

using namespace std;

typedef struct node // construct a node

{

int data;

int priority; // The lower the value, the higher wil be priority

struct node* next; // pointer to next node

} Node;

Node* newNode(int data_value, int Priority) // Function to create a new node

{

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = data_value;

temp->priority = Priority;

temp->next = NULL;

return temp;

}

int peek(Node** head) // return head node

{

return (*head)->data;

}

void pop(Node** head) // remove the element from the highest priority in the list

{

Node* temp = *head;

(*head) = (*head)->next;

free(temp); // free that node

}

void push(Node** head, int data_value, int p) // Function to push values in the ll according to priority

{

Node* start = (*head);

// Create new Node

Node* temp = newNode(data_value, p);

// Special Case: The head of list has

// Less priority than new nodes. So

// insert newnode before head node

// and change the head node.

if ((*head)->priority > p)

{

// Insert New Node before head

temp->next = *head;

(*head) = temp;

}

else

{

// Traverse the list and find a

// position to insert new node

while (start->next != NULL &&

start->next->priority < p)

{

start = start->next;

}

// Either at the ends of the list

// or at required position

temp->next = start->next;

start->next = temp;

}

}

int isEmpty(Node** head) // The function returns NULL if it is empty

{

return (*head) == NULL;

}

int main()

{

Node* pq = newNode(4, 1);

push(&pq, 5, 2);

push(&pq, 6, 3);

push(&pq, 7, 0);

// The priority queue created is 7 -> 4 -> 5 -> 2

while (!isEmpty(&pq))

{

cout << " " << peek(&pq);

pop(&pq);

}

return 0;

}

</code>

C Code

<code>

#include <stdio.h>

#include<stdlib.h>

typedef struct node // construct a node

{

int data;

int priority; // The lower the value, the higher will be priority

struct node* next; // pointer to next node

} Node;

Node* newNode(int data_value, int Priority) // Function to create a new node

{

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = data_value;

temp->priority = Priority;

temp->next = NULL;

return temp;

}

int peek(Node** head) // return head node

{

return (*head)->data;

}

void pop(Node** head) // remove the element from the highest priority in the list

{

Node* temp = *head;

(*head) = (*head)->next;

free(temp); // free that node

}

void push(Node** head, int data_value, int p) // Function to push values in the ll according to priority

{

Node* start = (*head);

// Create new Node

Node* temp = newNode(data_value, p);

// Special Case: The head of list has

// Less priority than a new node. So

// insert newnode before head node

// and change the head node.

if ((*head)->priority > p)

{

// Insert New Node before head

temp->next = *head;

(*head) = temp;

}

else

{

// Traverse the list and find a

// position to insert new node

while (start->next != NULL &&

start->next->priority < p)

{

start = start->next;

}

// Either at the ends of the list

// or at required position

temp->next = start->next;

start->next = temp;

}

}

int isEmpty(Node** head) // The function returns NULL if it is empty

{

return (*head) == NULL;

}

int main()

{

Node* pq = newNode(4, 1);

push(&pq, 5, 2);

push(&pq, 6, 3);

push(&pq, 7, 0);

// The priority queue created is 7 -> 4 -> 5 -> 2

while (!isEmpty(&pq))

{

printf("%d ",peek(&pq)) ;

pop(&pq);

}

return 0;

}

</code>

Output:

7 4 5 6

2. Binary heap - It is the most efficient variant of the priority queue. It has the following properties -

• It is a complete tree
• It is in the form of min heap or max heap.
• In a min binary heap, the root node is the smallest in the tree and the rest of the child nodes are greater than the root node.
• In a max binary heap, the root node is the largest among all the nodes.

Operations performed on a binary heap are as follows -

• insert(): Inserts a new element with a priority number assigned to it.
• extractMax(): Extracts an element from the heap with maximum priority.
• remove(i): Removes an element from the heap pointed by an iterator i.
• getMax(): Returns an element from the heap with maximum priority.
• changePriority(i, p): The function helps to change the priority of an element from i to p.

C++ Program to Implement Binary Heap

<code>

#include <bits/stdc++.h>

using namespace std;

int H[50]; // heap size is of 50 elements

int size = -1;

int parent(int i) // print the parent node of a given node

{

return (i - 1) / 2;

}

int leftChild(int i) // print index of a left child of given i node

{

return ((2 * i) + 1);

}

int rightChild(int i) // print index of a right child of given i node

{

return ((2 * i) + 2);

}

void shiftUp(int i) // shifts the node upwards according to the priority

{

while (i > 0 && H[parent(i)] < H[i]) {

// Swap parent and current node

swap(H[parent(i)], H[i]);

// Update i to parent of i

i = parent(i);

}

}

void shiftDown(int i) // shifts the node downwardds according to priority

{

int maxIndex = i;

// Left Child

int l = leftChild(i);

if (l <= size && H[l] > H[maxIndex]) {

maxIndex = l;

}

// Right Child

int r = rightChild(i);

if (r <= size && H[r] > H[maxIndex]) {

maxIndex = r;

}

// If i not same as maxIndex

if (i != maxIndex) {

swap(H[i], H[maxIndex]);

shiftDown(maxIndex);

}

}

void insert(int p) // insert a new element in this node

{

size = size + 1; // increase the heap size

H[size] = p;

// Shift Up to maintain heap property

shiftUp(size);

}

int extractMax() // extract the element with max priority

{

int result = H[0];

// Replace the value at the root

// with the last leaf

H[0] = H[size];

size = size - 1;

// Shift down the replaced element

// to maintain the heap property

shiftDown(0);

return result;

}

void changePriority(int i, int p) // change the priority accordingly

{

int oldp = H[i];

H[i] = p;

if (p > oldp) {

shiftUp(i);

}

else {

shiftDown(i);

}

}

int getMax() // find the value of current max element

{

return H[0];

}

void remove(int i) // remove the element at a given index i

{

H[i] = getMax() + 1;

// Shift the node to the root

// of the heap

shiftUp(i);

// Extract the node

extractMax();

}

int main()

{

insert(45); // insert element in the priority queue

insert(20);

insert(14);

insert(12);

insert(31);

insert(7);

insert(11);

insert(13);

insert(7);

int i = 0;

// Priority queue before extracting max element

cout << "Priority Queue : ";

while (i <= size) {

cout << H[i] << " ";

i++;

}

cout << "\n";

// Node with maximum priority

cout << "Node with maximum priority : "

<< extractMax() << "\n";

// Priority queue after extracting max

cout << "Priority queue after "

<< "extracting maximum : ";

int j = 0;

while (j <= size) {

cout << H[j] << " ";

j++;

}

cout << "\n";

// Change the priority of element

// present at index 2 to 49

changePriority(2, 49);

cout << "Priority queue after "

<< "priority change : ";

int k = 0;

while (k <= size) {

cout << H[k] << " ";

k++;

}

cout << "\n";

// Remove element at index 3

remove(3);

cout << "Priority queue after "

<< "removing the element : ";

int l = 0;

while (l <= size) {

cout << H[l] << " ";

l++;

}

return 0;

}

Output:

Priority Queue : 45 31 14 13 20 7 11 12 7

Node with maximum priority : 45

Priority queue after extracting maximum : 31 20 14 13 7 7 11 12

Priority queue after priority change : 49 20 31 13 7 7 11 12

Priority queue after removing the element : 49 20 31 12 7 7 11

For more examples, read this in-depth blog on Priority Queue by Scaler.

Applications of Priority Queue

• It is used in Dijkstra’s algorithm to find the shortest path between two nodes in a graph.
• It is used in Prim’s algorithm to find the MST in a weighted or undirected graph.
• It is used in Huffman coding and heap sort.
• It is used in operating system and A* search algorithm.

Conclusion

The priority queue is used to help with the problems that have priority related use cases. The major advantage of priority queue is we can access the highly prioritised element at O(1). The only drawback of priority queue is enqueue and dequeue operations take much higher time complexity due to matching the priority number.

To know more about data structure visit Scaler Topics Data Structures Resources (free).

Happy Learning!