September 28, 2010 Priority queues are a data structure in which
items arrive in random order and exit in priority order; they
provide the operations find-min, delete-min, insert and merge.
We implemented priority queues using leftist heaps in one
exercise and using pairing heaps in another exercise. In today’s
exercise, we will implement priority queues using the maxiphobic
heaps of Chris Okasaki. Maxiphobic heaps are a variant of
leftist heaps. Like leftist heaps, maxiphobic heaps are
represented as binary trees arranged according to the heap
property that every element is less than or equal to its two
children. Find-min looks at the root of the tree, delete-min
discards the root and merges its two children, and insert merges
the existing tree with a singleton tree containing the new
element. The key to leftist trees and maxiphobic trees is the
merge operation. In leftist trees, the rank of each left child
is always less than the rank of its sibling, where the rank of a
node is defined as the length of its