Indexed Priority Queue in C++

Basics

Priority queues are a useful data structure e.g. when you repeatedly need to access the largest or smallest element of a set of values but want more efficiency than keeping an array ordered. The C++ standard library contains std::priority_queue, which works well for basic use cases. It offers insertion of elements as well as access and removal of the minimum (or maximum). It does not, however, offer a method for changing the priority of a value, which is needed for some applications (like Dijkstra’s algorithm to find shortest paths in graphs). Often such a method is called decreaseKey or changeKey. This post offers an implementation using a binary heap which supports this operation in O(log(n)) time.

Code

The implementation makes it necessary to refer to specific elements with a numeric ID (or index) between 0 and maxSize-1. This maximum size of the priority queue must be specified when calling the constructor. The priority of IDs is specified with keys, which can be both simple numeric values (e.g. integers or floating point values) or custom classes for which operator< (for IndexedMaxPriorityQueue) or operator> (for IndexedMinPriorityQueue) is defined. The following main methods are available:

• insert to add a new ID
• peekFirst and removeFirst to view or remove the value with minimum/maximum priority
• remove to delete a specific ID
• changeKey to adapt the priority of an ID
• empty and contains to check for emptiness and whether a specific ID is part of the priority queue

The code needs C++17 and is available here: https://github.com/nspo/graphs-cpp/blob/master/general/include/IndexedPriorityQueue.h

You can also check out the test folder for some exampes.