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.
Efficient Union-Find in C++ – or: Disjoint-set forests with Path Compression and Ranks
tl;dr: https://github.com/nspo/graphs-cpp/blob/master/general/include/DisjointSets.h
Basics
Disjoint-set data structures are useful in cases where you have a (possibly very large) number of elements and want to repeatedly execute two operations: marking two elements as connected, and checking whether two elements are connected. A query of the latter kind does not necessarily mean that the two elements p and q were explicitly connected to each other by the caller – it is possible, e.g., that p was first connected to the element r, and only much later in time q was also connected to r.
The disjoint sets in the data structure are commonly represented by trees, where each node in the tree contains a link to its parent, the parent in turn contains a link to the parent’s parent, and so on. The node at the root of the tree contains contains a link to itself, i.e. it is its own parent. All nodes of a tree are in the same set. It can be easily checked whether two elements are in the same set by evaluating whether they have the same root. The set of trees is called the disjoint-set forest. While this approach is common and can be implemented efficiently, the C++ standard library does not contain an implementation – this post tries to offer one.
Let us assume the data structure is used for N elements, each having an index between 0 and N-1. The links to the parent nodes of all elements can then easily be saved in an array of length N. If parent[p] == q, then q is the parent of p. Whenever two sets containing the elements p and q should be merged, this can be achieved by attaching the root of one element to the root of the other.
