A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.

However, some algorithms demand updating the values of elements while they are in the priority queue (eg., edge relaxation in Dijkstra’s shortest path algorithm). This cannot be provided with a simple heap-based implementation and requires augmenting the heap with indexing. Each key is associated with an index. The heap stores the indices and not the keys themselves. An inverse mapping of indices stored in heap is also maintained; it gives the position in the heap where an index of a key is currently stored. Together, they enable efficient updation of key values and also deletion of keys not on top of the heap.

**Space Complexity:** O(N)

**Time Complexity:**

- Accessing the minimum key: O(1)
- Inserting a key: O(log N)
- Deleting the minimum key: O(log N)
- Deleting any key: O(log N)
- Updating (Increasing/Decreasing) value of any key: O(log N)

**Some applications:**

- Dijkstra’s single source shortest path algorithm
- Prim’s Minimum Spanning Tree algorithm
- Finding the median of a dynamic list

Take a look at the C++ implementation.

**Reference:** Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

Pingback: Median of a dynamic list | Everything Under The Sun

Pingback: Prim’s Minimum Spanning Tree Algorithm | Everything Under The Sun

Pingback: Dijkstra’s single source shortest path algorithm | Everything Under The Sun

Pingback: Multiway Merge : merging m sorted lists | Everything Under The Sun

Pingback: Interval Partitioning Problem | Everything Under The Sun

Thanks for implementation

Pingback: Problem of the day: Queue with min operation | Everything Under The Sun