Data structures: Pairing Heap

Recently, I came across a neat data structure called a pairing heap. Now, if you’re not familiar with the term heap it can sound confusing. That’s because it doesn’t mean much. A heap is basically a set of objects with some kind of ordering that we don’t have an intuitive word for. Discard any notions of a heap as a pile of stuff. Specifically, it is a hierarchical tree (or forest) where each parent has a certain relationship to its children (like being less than them).

Pairing heaps are used for an efficient implementation of a priority queue. A priority queue keeps track of the minimum of a set of objects, so every time you take something off the queue it is always the lowest value. Priority queues are most notably used when implementing Dijkstra’s algorithm to find the shortest path in a graph. A lot of useful algorithms are based on Dijkstra’s algorithm, including one to compute geodesic distances on meshes which is what we are using pairing heaps for.

Pairing heaps are neat because they are simple to implement and perform well in real applications. Specifically, they perform very well in amortized time. Meaning that while an individual operation may take a longer time, the aggregate of all the operations over the entire life cycle of queue is fast. They have similar properties to the more well known Fibonacci heap, but they are easier to code and often perform better.

Pairing heaps have very simple properties. Each heap is associated with an object or value. Each heap also has a set of child heaps. The value of the object is always less than (or greater than) that of its child heaps. That’s it.

The heap has a few basic operations:

min(heap) – Get the smallest value. Easy. Just look at the value at the top of the heap.

merge(heap1, heap2) – Combine two heaps. Add the heap with greatest value to the children of the other heap. Also fast.

insert(heap, value) – Add a new value. Merge the heap with a new heap only containing the new value.

removeMin(heap) – Remove the smallest object. A little more complicated. Recursively merge all the child heaps in pairs. The result is your new heap.

decreaseKey(heap, subheap, new_value) – Decrease the value of an object in the heap. removeMin on the subheap of the value you are replacing. Insert the new value into to top of the heap.

Here’s a gist of an implementation of a pairing heap in javascript