Randomized Meldable Heaps: An alternative tree structure for the implementation of priority queue

mgcadmin 20-08-2022

Randomized Meldable Heaps

When it comes to priority queues, the binary heap is the go-to data structure when it comes to implementation, and with good reason. Binary heaps offer worst-case logarithmic complexity for all operations that it supports. Despite its popularity, it does have some draw backs. The upheap/downheap operations that drive binary heaps while not being altogether difficult, they are abstract enough to make their implementation non-trivial. In several areas a simple sorted linked list offers superior performance to a binary heap - specifically findMin() and popMin() are both O(1) in a sorted linked list vs O(log n) for the binary heap (It is binary heaps O(log n) insertion vs the sorted linked lists O(n) that drives part of the binary heaps popularity). And while merging two sorted linked lists is a simple affair, there is no efficient way to merge two array based binary heaps efficiently.

While being the most popular, binary heaps are from the only heap-ordered priority queue structure however. Fibonacci heaps and Binomial Queue's are two very high performance alternatives, though their implementation is not for the faint of heart. There is another option however, and it is the topic of this article: The Randomized Meldable Heap (RMH).

Another Way

Like their array based cousin, RMH's are implemented via a binary tree. Unlike binary heaps however, RMH's have relaxed the requirement of the binary tree being a complete binary tree, and a pointer based tree is used instead of the binary heaps traditional array based approach.

The central operation that runs the whole show in an RMH is the Merge() - or meld - operation, which is easily recursively implemented:

Because our tree is heap ordered, the getMin() operation is an O(1) operation, we simply return the root nodes value.

The popMin() operation is simple, we save the root node's value to be returned, and set root the root of the tree to the result of merging the current root nodes left and right child.

Adding a node to the heap is like wise simple, we create a new node with the value we want to add to the heap and once again call the merge function on our new node and the root node.

Due to merge() having O(log n) complexity, all operations (with the exception of the O(1) getMin() operation) execute with O(log n) complexity - on par with, and in some instances better than a traditional binary heap.

A Full implementation is as Follows:

What makes the Randomized Meldable Heap special is that two of them can be efficiently merged by calling merge with their respective root nodes as the arguments. In order for two heaps to be merged, we need a way to expose the root node of the tree, this serves as our "door" in to the data structure its self, which justifies the public method PQ::rootNode() which simply returns the root node of the tree. Coincidentally, exposing the root node also allows to perform a breadth first (level order) traversal of the tree to examine the contents of the heap.

Using the following piece of code, we will take two strings, each string being used to make its own heap. We well then merge the two heaps, and use our augmented breadth first traversal to examine the layout of each heap:

Running the above code produces the following output:

[maxs-MacBook-Pro:~]% ./"testrmh" 
Heap produced by the characters of the string "APRIORITYQUEUEEXAMPLE"
A 
E A 
M E E 
I L E 
O U U I P 
R X P Q 
T R Y 

Heap produced the characters of the string "RANDOMMELDABLEHEAPMERGE"
A 
A G 
B A M 
E D D R P 
H E E E 
M L E M L 
N R O 

The product of merging the two heaps shown: 
A 
A A 
A G E E 
B A M I L E 
E D D R P O U U I P 
H E E E R X P Q 
M E E M L T R Y 
N L R O 
M 

Popping heap till empty: 
A A A A A B D D E E E E E E E E E G H I I L L L M M M M N O O P P P Q R R R R T U U X Y

 

Wrapping Up

And their you have it, Randomized Meldable Heaps. This data structure can function much as a drop in replacement for std::priority_queue, and my personal experiencing using it as the priority queue for Dijkstra's algorithm produced favorable results. While not shown here, decreaseKey() can also be implemented efficiently, a method which std::priority_queue is lacking.

---