Programming Praxis

A priority queue, or heap, is a data structure that accepts items in any order and emits them in sorted order. In previous exercises we have implemented priority queues using leftist heaps, pairing heaps, and maxiphobic heaps, and we have used them in sorting algorithms, a prime number generator, calculating the minimum spanning tree of a graph, apportioning representation in the U. S. House of Representatives, and the streaming median. In today’s exercise we look at yet another implementation of priority queues, using binomial heaps that we steal from Chris Okasaki’s book Purely Functional Data Structures; as an alternative to the book, you can read Okasaki’s paper at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973.

Binomial heaps are lists of binomial trees, which consist of a rank, an element, and a list of child trees and are defined by a base rule and a recursive rule: A binomial tree of rank 0 is a singleton node. A binomial tree of rank r + 1 is made by linking two binomial trees of rank r by making one tree the left most child of the other. Each list of child nodes is maintained in decreasing order of rank; heap order is maintained by linking trees with larger elements under trees with smaller elements. No two sibling trees have the same rank. A consequence of the linking behavior is that all trees contain 2^r elements.

Insertion is simple enough. First the item being inserted is made into a singleton heap of rank 0. Then the new heap is inserted by stepping through the existing trees in increasing order of rank, linking trees of equal rank along the way, until a missing rank is found. Merging two heaps is similar, stepping through both lists of trees, linking trees of equal rank. The worst case of insertion occurs with a heap of size 2^k − 1, which requires O(k) = O(log n) time; a similar analysis applies to merging.

The find-min and remove-min operations both call an auxiliary function that finds the tree with the minimum element at its root and returns both that tree and the list of remaining trees. Find-min simply returns the minimum element. Delete-min discards the element at the root of the minimum tree, then merges its children with the list of remaining trees. Both the auxiliary function and the delete-min function operate in time O(k) = O(log n), and find-min operates in time O(1) once the auxiliary function runs.

Your task is to implement a function library for priority queues using binomial heaps. 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