Priority Queue
An ordinary queue follows FIFO — the first element to be inserted comes out first. A priority queue introduces the idea of priority which is attached to each item. It contains items that are ordered by priority.
Why use it?
Let’s say that we have a continuous stream of inputs and we’d like to store them in order by priority. That way, we can perform the most vital task in OS first, for example. It would be helpful to analyse the time complexity for each ADT to better understand why we ever need a priority queue.
- A vanilla sorted array: It takes O(logN) to find a place to insert an item. Inserting an element with the highest priority to the beginning of the array requires the shift of N elements to the right, which is quite a heavy work especially when N is huuuge. Thus, the time complexity is O(N).
- A linked list: While inserting a node only takes O(1) itself, searching through linked nodes requires O(N).
- A vanilla queue: Enqueueing and dequeueing an item only take O(1), but finding an item with the highest priority requires a sort, which takes O(NlogN) at best.
This is where a priority queue comes into play. Insertion and search only take (logN) at worst.
Let’s take another example where a priority queue shines particularly.
In this case, Elementary PQ is implemented by a simple array.
That uses an unordered array takes O(1) to insert an item while dequeue takes O(M) since we should search through all the elements to find the max or min. In this way, to build a simple PQ, it takes O(MN) as we should iterate through all the N items and insert it with O(M).
On the other hand, you can implement a priority queue with an ordered array. Each time you insert an item, you sort the array. It takes O(1) in result to dequeue an item.
While the use of an elementary PQ may have marginal benefit to time complexity over Array & Sort, it certainly reduces the extra memory from N to M.
There’s a more room for improvement.
Binary Heap
It’s built upon a complete binary tree whose each level is completely filled except possibly for bottom level where all nodes are filled from far left.
