Indexed Min-Priority Queue C++ implementation

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:

Take a look at the C++ implementation.

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

7 thoughts on “Indexed Min-Priority Queue C++ implementation

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

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

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

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

  5. Pingback: Interval Partitioning Problem | Everything Under The Sun

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s