Priority Queues

excerpt: What is a priority queue? How can we implement it? What is the time complexity of different approaches to implement the priority queues?

Priority Queue is an abstract data type. A priority queue assigns a priority to every item in the queue. The dequeue method removes the item that has the highest priority. The items with high priority are handled first.

Priority Queue ADT

The operations of priority queue ADT are:

• add(key)
• remove_min
• peek
• contains?(element)
• remove(element)

One way to implement a priority queue is to keep the items in the queue sorted by priority. The main concept behind insertion sort can be used to keep the items sorted. Adding a new item to the queue requires searching through the queue to find the position where it belongs and insert the item in that position. The dequeue method will remove the top item from the queue. The time complexity of this approach for enqueue operation is O(N) and dequeue operation is O(1) time.

Another approach is to store the items in the same order they are added to the queue and then have the dequeue method search for the highest priority item. The time complexity of this approach is O(1) time for enqueue and O(N) for dequeue.

These two approaches are straightforward to implement with linked lists. The heap data structure provides a more efficient way of implementing a priority queue. A heap based priority queue can enqueue and dequeue in O(log N) time.

A complete binary tree is a binary tree of height h such that every level less than h is full and all nodes at level h are as far to the left as possible. Min heap is a complete binary tree with unique comparable elements, such that each node’s element is less than its children’s element.