The priority queue in a data structure is used in Google Maps for searching the optimal path to reach any destination. Dijkstra’s Shortest Path algorithm utilizes a min priority queue to store all possible paths to reach the destination, considering distance as a parameter for priority assignment. In the end, it will return the element with the highest priority as the optimal route. So, in this tutorial, you will discover priority queue in data structure to understand their functionalities and applications.
Introduction to Priority Queue in Data Structure
Priority Queue is an abstract data type that performs operations on data elements per their priority. To understand it better, first analyze the real-life scenario of a priority queue.
The hospital emergency queue is an ideal real-life example of a priority queue. In this queue of patients, the patient with the most critical situation is the first in a queue, and the patient who doesn’t need immediate medical attention will be the last. In this queue, the priority depends on the medical condition of the patients.
The priority queue in data structure resembles the properties of the hospital emergency queue. Thus, it is highly used in sorting algorithms. It behaves similar to a linear queue except for the fact that each element has some priority assigned to it. The priority of elements determines the order of removal in a queue, i.e., the element with higher priority will leave the queue first, whereas the element with the lowest priority at last.
Characteristics of Priority Queue
Priority queue in a data structure is an extension of a linear queue that possesses the following properties:
- Every element has a certain priority assigned to it.
- Every element of this queue must be comparable.
- It will delete the element with higher priority before the element with lower priority.
- If multiple elements have the same priority, it does their removal from the queue according to the FCFS principle.
Now, understand these properties with the help of an example. Consider you have to insert 7, 2, 45, 32, and 12 in a priority queue. The element with the least value has the highest property. Thus, you should maintain the lowest element at the front node.
The image above shows how it maintains the priority during insertion in a queue. But, if you carry the N comparisons for each insertion, time-complexity will become O(N^2).
Representation of Priority Queue
You can also implement a priority queue using arrays, however, if you consider array implementation of the priority queue, then inserting elements into the sorted array will cost you O(n). In general, processing each element will further cost you O(n^2). Because of this complexity, implementing a priority queue using arrays is not an ideal approach. Hence, you will only learn about the representation of the priority queue using a linked list.
Consider a linked queue having 3 data elements 3, 17, 43, respectively. It arranges all these elements according to priority. But, what if you have to insert a new node into the linked queue consisting of value 2? Since 2 is smaller than the element at the front (head) node, insertion from the front will be more efficient. Additionally, it will allow you to have O(1) time-complexity during deletion.
The diagram above shows how it will insert the new node consisting of elements in a linked queue. This particular scenario of insertion seems perfect as it doesn’t cost you more time. But what if the element is significantly larger than all the nodes of a queue?
For instance, say you want to insert a node consisting of element 45. Here, it will compare element 45 with each element inside the queue. However, this insertion will cost you O(N). Representation of the linked queue below displays how it will insert element 45 in a priority queue.
Different Implementation Strategies for Priority Queue
Three approaches implement a priority queue in data structure with a complexity less than O(n^2). They are shown in the table below:
Binary heap and binary tree provide almost similar complexities. These approaches cost you O(logn) for insertion and deletion and O(1) for peek operation. But, which approach is the best to implement a priority queue?
To answer this question, you need to explore memory management in the case of both data structures. Since binary heap utilizes arrays, there is always a better locality of reference, and operations become more cache-friendly. Whereas, the Binary search trees use pointers to implement front and rear nodes, which takes up more space in memory. Hence, building a self-balancing BST’s cost O(NlogN) where binary heap just costs you O(n). These facts clarify that the Binary Heap is the best data structure for priority queue implementation.
Moving forward, you will understand what heap data structure is and how it works.
What is Heap?
A heap is a tree-like data structure that forms a complete tree and satisfies the heap invariant. The heap invariant states that, if A is a parent node of B, then A is ordered with respect to B for all nodes A and B in a heap. This means a parent node’s value is always greater than or equal to the value of the child nodes for all nodes in a heap. Or the value of the parent node is less than or equal to the value of the child node for all nodes in a heap.
Additionally, there are two types of heap data structures, termed Max Heap and Min heap. The Max heap is a tree-like structure in which the parent node’s value is greater than the value of the child node. The diagram given below represents a binary max heap having the highest value at its root node.
The Min heap is a tree-like structure in which the parent node’s value is smaller than the value of the child node. The tree diagram given below shows a binary heap tree having the smallest value at its root node.
Types of Priority Queue
There are two types of priority queues based on the priority of elements.
- If the element with the smallest value has the highest priority, then that priority queue is called the min priority queue.
- If the element with a higher value has the highest priority, then that priority queue is known as the max priority queue.
- Furthermore, you can implement the min priority queue using a min heap, whereas you can implement the max priority queue using a max heap.
Priority Queue Operations
The operations that you can perform on a priority queue in data structure are insertion, deletion, and peek. Let’s analyze how you can achieve these operations on max heap representation of priority queue.
- Inserting the Element in a Priority Queue: Once you perform the new insertion, the new element will move to the empty space from top to bottom and left to right. Additionally, if the element is not in the correct position, it will compare it with the parent node. Following that, if the element is not in proper order, then it swaps the elements. The swapping process continues until all the elements inside the queue are in the correct positions.
In the example above, it inserted the new element 43 into the max heap representation of the priority queue. But because of this insertion, the order gets disturbed. To make sure that all the elements arrive in proper order, a swapping operation takes place. This operation is also known as Heapify in the Heap data structure.
- Deletion in Priority Queue: As you know that in a max heap, the maximum element is the root node. And it will remove the element which has maximum priority first. Thus, you remove the root node from the queue. This removal creates an empty slot, which will be further filled with new insertion. Then, it compares the newly inserted element with all the elements inside the queue to maintain the heap invariant.
In the example above, it will delete the element at the root node, and the heapify operation is performed to restore the priority-based order.
Coding Implementation of Priority Queue
Here, you will implement a priority queue in data structure using a max heap. The language that you are going to use for implementation is the C programming language.
|
#include <stdio.h> #include <stdlib.h> struct heap { int size; int count; int *heaparr; }; int *heap, size, count; int initial_size = 4; void heap_init(struct heap *h) { h->count = 0; h->size = initial_size; h->heaparr = (int *) malloc(sizeof(int) * 4); if(!h->heaparr) { printf("Error allocating memory...\n"); exit(-1); } } void max_heapify(int *data, int loc, int count) { int left, right, largest, temp; left = 2*(loc) + 1; right = left + 1; largest = loc; if (left <= count && data[left] > data[largest]) { largest = left; } if (right <= count && data[right] > data[largest]) { largest = right; } if(largest != loc) { temp = data[loc]; data[loc] = data[largest]; data[largest] = temp; max_heapify(data, largest, count); } } void heap_push(struct heap *h, int value) { int index, parent; // Resize the heap if it is too small to hold all the data if (h->count == h->size) { h->size += 1; h->heaparr = realloc(h->heaparr, sizeof(int) * h->size); if (!h->heaparr) exit(-1); // Exit if the memory allocation fails } index = h->count++; // First insert at last of array // Find out where to put the element and put it for(;index; index = parent) { parent = (index - 1) / 2; if (h->heaparr[parent] >= value) break; h->heaparr[index] = h->heaparr[parent]; } h->heaparr[index] = value; } void heap_display(struct heap *h) { int i; for(i=0; i<h->count; ++i) { printf("|%d|", h->heaparr[i]); } printf("\n"); } int heap_delete(struct heap *h) { int removed; int temp = h->heaparr[--h->count]; if ((h->count <= (h->size + 2)) && (h->size > initial_size)) { h->size -= 1; h->heaparr = realloc(h->heaparr, sizeof(int) * h->size); if (!h->heaparr) exit(-1); // Exit if the memory allocation fails } removed = h->heaparr[0]; h->heaparr[0] = temp; max_heapify(h->heaparr, 0, h->count); return removed; } int emptyPQ(struct heap *pq) { int i; while(pq->count != 0) { printf("<<%d", heap_delete(pq)); } } int main() { struct heap h; heap_init(&h); heap_push(&h,1); heap_push(&h,5); heap_push(&h,3); heap_push(&h,7); heap_push(&h,9); heap_push(&h,8); heap_display(&h); heap_display(&h); printf("\nThe deletion of elements from priority queue depending on priority: \n"); emptyPQ(&h); return 0; } |
Output: You have implemented a priority queue in data structure. It will remove the elements of a priority queue as per their priority. You can verify that with the help of the result shown below:
Applications of Priority Queue in Data Structure
The following are the applications of the priority queue in data structures:
- IP Routing to Find Open Shortest Path First: OSPF is a link-state routing protocol that is used to find the best path between the source and the destination router. This protocol works on the principle of Dijkstra’s shortest path algorithm by using a priority queue to track an optimal route.
- Data Compression in WINZIP / GZIP: The Huffman encoding algorithm uses a priority queue to maintain the codes for data contents. They store these codes in a min heap, considering the size of codes as a parameter to decide the priority.
- Used in implementing Prim’s algorithm: Prim’s algorithm generates a minimum spanning tree from an undirected, connected, and weighted graph. It uses a min priority queue to maintain the order of elements for generating a minimum spanning tree.
- Used to perform the heap sort: When you provide an unsorted array to this algorithm, it converts it into a sorted array. This algorithm uses a min priority queue to generate an order of elements.
- Load balancing and Interrupt handling: Load balancing fields the requests from the users and distributes them to different available servers. Whereas, interrupt handling is a mechanism for handling interrupts in OS. The priority queue is used to manage requests, and it interrupts both functionalities simultaneously.
Conclusion
In this tutorial, you explored the priority queue in data structure. You went through different implementation strategies that can implement a priority queue. Out of which, the heap implementation is the optimal approach. Following this, you understood the priority queue operations with the help of a pictorial representation. You also encountered coding implementation of the priority queue in data structure.
If you are looking for more comprehensive learning that goes beyond data structures and covers the most in-demand programming languages and skills needed today to build interactive applications, Simplilearn’s Software Development Courses will prove to be just right for you.
The courses mentioned in the catalog above will help you master the art of Software Development and become job-ready. Explore now and get started!
On that note, do you have any questions related to this tutorial on a priority queue in data structure? If you do, please place them as comments towards the end of this page; we will respond to them soon!