Priority Queues
This article will build upon my previous article on heaps. As a refresher, a heap is a special kind of binary tree that follows a set of rules. A heap can be a max heap which will have their biggest value as the root and the value of each parent node is always greater than its child nodes. Otherwise, it is a min heap which will have their smallest value as the root and the value of each parent node is always smaller than its child nodes. Heaps have no implied ordering between siblings.
Priority queue is one of the most useful implementations of a heap. A priority queue is a data structure where each element has a priority and a value. Just like heaps, there are two kinds of priority queues: a max-priority queue and a min-priority queue. For a max-priority queue, elements with higher priorities are served before elements with lower priorities. Vice versa for min-priority queue.
A common real-life example of a priority queue would be a hospital queue where the patient with the most critical situation would be the first in the queue. In this case, the priority order is the situation of each patient.
Implementations
Priority queues can be implemented using common data structure like arrays, linked lists, heaps, and binary trees. Priority queues are connected to heaps since heaps provide an efficient implementation of priority queues.
Operations and Big O
Peek — returns the maximum element from max-priority queue or minimum element from min-priority queue without deleting the node. Takes constant O(1) time.
Insert — add an element to the priority queue. Similar to the Insertion section of my Heaps article. Takes logarithmic O(log n) time since a new priority element would have to be assigned, and the height of the heap readjusts.
Delete — removes the largest element from the max priority queue or removes the smallest element from the min priority queue. Similar to Removing the biggest element section of my Heaps article. Takes logarithmic O(log n) time since a new priority element would have to be assigned, thus readjusting the height of the heap.
Applications
Dijkstra’s Shortest Path Algorithm using priority queue: can extract the minimum from a graph that is stored in the form of adjacency list or matrix efficiently when implementing Dijkstra’s algorithm.
Prim’s algorithm: store keys of nodes and extract minimum key node at every step.
Huffman codes: used to compresses data.
A* Search Algorithm: used to keep track of unexplored routes, the one for which a lower bound on the total path length is smallest is given highest priority. The A* search algorithm finds the shortest path between two vertices of a weighted graph, trying out the most promising routes first.
Heap Sort: typical implementation of Priority Queue.
Resources
For more resources on Priority Queues, I suggest looking at these helpful links.
My heap article: https://chandler-hanson.medium.com/heap-heap-heap-d423320a4997
https://datastructures.maximal.io/priority-queues/
https://www.geeksforgeeks.org/implementation-priority-queue-javascript/
https://medium.com/@angeloacebedo/an-intro-to-priority-queues-a28c2e09db70
https://medium.com/basecs/learning-to-love-heaps-cef2b273a238
https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/
