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)
- 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)
- 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.