Pairing Heaps

August 14, 2009

We previously implemented priority queues using leftist heaps. In this exercise we will implement the same library using a different data structure known as a pairing heap. Pairing heaps are an unusual data structure; they are simple to implement, and performance is good, but their time complexity is not proved, only conjectured, and the analysis has defied many good algorithmists. Our presentation is based on Chris Okasaki’s book Purely Functional Data Structures.

Pairing heaps are heap-ordered multi-way trees, with each node of each tree less than its children. A pairing heap is either empty or is a node consisting of an item and a list of pairing heaps, none of which may be empty. The find-first function simply returns the item at the root of the tree of nodes. Merge takes two trees and makes the tree with the larger root the leftmost child of the tree with the smaller root. Insert builds a singleton node, then calls merge.

The fundamental operation on pairing heaps is the delete-first operation, which discards the root of the tree and merges its children in two passes. The first pass runs from left to right, merging child nodes pair-wise, the first child with the second, the third child with the fourth, and so on. The second pass merges the resulting trees, again pair-wise, from right to left.

Your task is to implement priority queues using pairing heaps, using the same interface as the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

Update: The Daily WTF

August 14, 2009

Alex Papadimoulis has agreed to change the name of his series of programming exercises, thus ending the dispute between us. I thank him for agreeing to the change, and wish him well.

To all of my regular readers: I apologize again for involving you in this dispute. The next exercise will be published in a few hours, and I hope you are as anxious to get back to programming as I am.

To all those people who found my blog for the first time: Welcome! Please stay. Enjoy the exercises. And please post your solutions, so we may all learn from your work.