# Data Structure: Max Priority Queue

Data structure

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)