An Intro to Priority Queues

Disclaimer: this article assumes you already know the function of a max/min heap and the purpose of heapify().

Concept

While stacks have a last-in-first-out (LIFO mechanism) and queues have a first-in-first-out mechanism (FIFO), priority queues are somewhat different. Just by the name itself, a priority queue is just a queue — with the added extension of associating a “priority” to each item in the queue. Just like queues, priority queues also have a FIFO mechanism.

But what does “priority” mean in this case? What does it mean to assign a “priority” to an item in the queue?

The purpose of priority queues is to insert/remove the largest/smallest item. The higher the priority of an item in the queue, the earlier in the order it will be removed.

Since we’re dealing with removing the largest or smallest item, a really efficient way of implementing a priority queue is by using a max/min heap. This is because the max/min root element is already at the root node of the entire tree, so when your heap structure is properly ordered, the function of priority queues follows through naturally.

After heapifying your heap, it takes only O(1) operations to access the maximum or minimum value in a max/min heap. In this case, you could say that you’re treating the heap like it’s a queue — you “pop” (dequeue) the first element, aka the root element. The highest priority items are always at the front of the queue, and the lowest priority towards the back.

Here are the 3 main properties of a priority queue:

1. Every item is associated with a priority.
2. An item with a high priority is removed first before an item with a lower priority.
3. If 2 elements have the same priority, they are removed according to their order in the queue.

Operations

When implementing a priority queue using a binary max/min heap, here are the possible operations you can invoke on a priority queue, along with their run-times.

• getHighestPriority() — returns the element with the highest priority, aka the max/min element. Root element if using a max/min heap. Takes constant O(1) operations.
• insert() — inserts a new element, reevaluating the priority value of the highest priority element. Takes logarithmic O(log n) time since a new priority element would have to be assigned, and the height of the heap readjusts according to whether n stays as a power of 2.
• deleteHighestPriority() — deletes the element with the highest priority, so the root element in the binary heap gets deleted. Similarly to insert(), this takes O(log n) time since a new priority element would have to be assigned, thus readjusting the height of the heap.

Conclusions

• The purpose of a priority queue is to insert/remove the maximum or minimum item.
• Higher priority items are at the front of the queue, and the lowest priority items are at the back.
• Binary max/min heaps are a very efficient way to implement priority queues due to their runtimes.
• Normally, it would take O(n) to insert into a list, and O(n log n) operations to sort a list. Using a binary heap for priority queues makes both insertion and sorting easier: it only takes O(log n) operations to enqueue and dequeue items.

Sources:

Priority Queue | Set 1 (Introduction) - GeeksforGeeks

Python Tutorial: Data Structure - Priority Queue & heapq - 2018