The Pairing Heap, Part 1 | Jim's Random Notes

A key takeaway from my early discussion of heaps is that if all we need is the ability to get the smallest item whenever we reach into the bag, then there’s no need to keep the entire bag in sorted order if some less expensive alternate ordering will work. Because of that relaxed requirement, we can implement a priority queue with a heap a whole lot more efficiently than with a sorted list.

I like to call it creative laziness.

Binary heaps are useful and quite efficient for many applications. For a pure priority queue, it’s hard to beat the combination of simplicity and efficiency of a binary heap. It’s easy to understand, easy to implement, and performs quite well in most situations. But the simplicity of the binary heap makes it somewhat inflexible, and also can prove to be inefficient when heaps become very large.

Even though the binary heap isn’t sorted, its ordering rules are pretty strict. If you recall, a valid binary heap must satisfy two properties:

The heap property: the key stored in a node is greater than or equal to the key stored in the parent node.
The shape property: it’s a complete binary tree.

Maintaining the shape property is required if you want to efficiently implement the binary heap in a list or array, because it lets you implicitly determine the locations of the child or parent nodes. But nothing says that you have to implement a binary heap in an array. You could use a more traditional tree representation, with explicit nodes that have right, left, and parent node references. That has some real benefits.

For example, a common extension to the priority queue is the ability to change the priority of an item in the queue. It’s possible to do that with a binary heap, and in fact isn’t difficult. It’s inefficient, though, because in a binary heap it takes a sequential search to find the item before you can change its priority.

But if you have a traditional tree representation, then you can maintain direct references to the nodes in the heap. At that point, there’s no longer a need for the sequential search to find the node, and changing an item’s priority becomes a pure O(log n) operation. Algorithms such as the A* search algorithm typically use something other than a binary heap for their priority queues, specifically because changing an item’s priority is a common operation.

Another common heap operation is merging (also known as melding): combining two heaps into one. If you have two binary heaps, merging them takes time proportional to the combined size of both heaps. That is, it takes O(n + m) time. The basic idea is to allocate an array that’s the size of both heaps, put all the items into it, and then call a BuildHeap function to construct the heap. With a different heap representation, you can do the merge in constant time.

It turns out that maintaining the shape property when you go to a more traditional tree representation is needlessly expensive. If you eliminate the need for the shape property, it becomes possible to indulge in even more creative laziness.

And, my oh my, have people been creative. Here’s a partial list of heap implementations.

There’s a lot of discussion about which of those is the “fastest” or “best” heap implementation. A lot of it involves theoretically optimum asymptotic behavior, and can get pretty confusing for those of us who just want a working heap data structure that performs well in our applications. Without going into too much detail, I’ll just say that some of those heap implementations that have theoretically optimum performance in some areas (the Brodal queue, for example) are difficult to implement and not at all efficient in real-world situations.

Of those that I’ve worked with, I particularly like Pairing heap because of its simplicity.

The pairing heap’s shape is much different than that of a binary heap. Rather than having right and left child references, a pairing heap node maintains child lists. It maintains the heap property in that any child in a min-heap is greater than or equal to its parent, but the concept of shape is thrown out the window. For example, consider this binary heap of the numbers from 0 to 9.


                    0
              1           3
          5       2   7       4
        9   6   8

Again, in the binary heap, each node has up to two children, and the children are larger than the parents. Although there are multiple valid arrangements of values possible for a binary heap, they all maintain that shape property.

A Pairing heap’s structure is much more flexible. The smallest node is always the root, and children are always larger than their parents, but that’s where the similarity ends. The best way to describe the structure is to go through an exercise of adding and removing items.

If you start with an empty heap and add an item, then that item becomes the root. So, let’s add 6 as the first item in the heap:

Now, we add the value 3. The rules for adding are:

If there is no root, then the new item becomes the root.
If the new item is greater than or equal to the root, then the new item is added to the root item’s child list.
If the new item is smaller than the root, then the new item becomes the root, the old root’s child list is appended to the new root’s child list, and the old root is appended to that child list.

In this case, 3 is smaller than 6, so 3 becomes the root and 6 is added as a child of 3.

    3
    |
    6

Here, the vertical bar character (|) is used to denote a parent-child relationship. So node 6 is a child of node 3.

Now we add 4 to the heap. Since 4 is larger than 3, 4 is added to the child list.

    3
    |
    6,4

When we add 2 to the heap, 2 becomes the new root, and 3 is appended to the child list:

    2
    |
    6,4,3

I’ll add 5, 8, 9, and 7 in that order, giving:

    2
    |
    6,4,3,5,8,9,7

Adding 0 makes 0 the root, and then adding 1 appends to the child list:

    0
    |
    6,4,3,5,8,9,7,2,1

Note that the heap property is maintained. The smallest item is at the root, and child items and their siblings are larger than their parents. Because the smallest item is at the root, we can still execute the get-minimum function in constant time.

And in fact, insert is also a constant time operation. Inserting an item consists of a single comparison, and appending an item to a list.

Things get interesting when we want to remove the smallest item. Removing the smallest item is no trouble at all, of course. It’s figuring out the new root that gets interesting. This proceeds in two steps:

First, process the children in pairs from left to right, creating 2-node heaps with the lowest item at the root, and the other item as a child. So using the child list above, we would create:

    4 3 8 2 1
    | | | |
    6 5 9 7

So 6 is a child of 4, 5 is a child of 3, etc. In this case, 1 doesn’t have a child.

Then, we process from right to left, taking the lower item as the root and adding the other item as a child of the root. Starting with 1 and 2, we combine them to create:

Proceeding to compare 1 and 8:

Note here that 2 and 8 are siblings, but 7 is a child of 2, and 9 is a child of 8. 9 and 7 are not siblings.

When we’re done processing, we have:

Again, the heap property is maintained.

It’s very important to understand that the heap property is maintained. All child nodes are larger than their parent nodes. Siblings (children of the same node) are represented in an unordered list, which is just fine as long as each sibling is larger than the parent node. Also, a node’s children only have to be larger than their parent node. Being smaller than a parent’s sibling does not violate the heap property. In the figure above, for example, 5 is larger than its parent, 3, but smaller than its parent’s sibling, 8.

Removing 1 from the heap leaves us with

    2, 8, 3, 4
    |  |  |  |
    7  9  5  6

Again, we pair from left to right. 2 is smaller than 8, so 2 becomes the root of the subtree. But what happens to the children? They’re appended to the child list of the other node. So pairing 2 and 8 results in:

And pairing the others gives:

    2      3
    |      |
    8, 7   4, 5
    |      |
    9      6

And combining from right to left makes 2 the root of the new tree:

Again, you can see that the heap property is maintained.

Now, when we remove 2 from the heap, we first pair 8 and 7 to create:

And then combine to form:

When 3 was selected as the smallest item, node 7 was appended to the child list.

That’s the basics of the Pairing heap. You might be asking yourself how that can possibly be faster than a binary heap. That will be the topic for next time.