Today I will implement another important abstract data type – priority queue. Priority queues are used:

• in heap sort
• to track top N elements in a very long sequence
• to merge K ordered sequences and produce single ordered sequence

Usually priority queues have following functions:

• insert() – to add new item with a priority
• deleteMin() or deleteMax() – to remove an item with min/max priority
• findMin() or findMax() – to get an item with min/max priority
• length() – to get the number of items in the priority queue

As a foundation I’ll use in the last post described efficient data structure – binary heap (in fact, max-heap). Overall, priority queue can be seen as a generalization of stack and queue data structures. Stack can be implemented as a max priority queue where priority of each inserted element is monotonically increasing and queue – where priority of each inserted element is monotonically decreasing.

The implementation of max priority queue (tests) is almost identical to the max-heap implementation:

Complexity:

• insert - O(logn)
• deleteMin/deleteMax - O(logn)
• findMin/findMax - O(1)