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 IDpeekFirst
andremoveFirst
to view or remove the value with minimum/maximum priorityremove
to delete a specific IDchangeKey
to adapt the priority of an IDempty
andcontains
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.
Leave a Reply