Merging priority queues - Data Structures and Problem Solving Using Java - page 872

logarithmic. However, it supports all operations in logarithmic amortized
time. The skew heap is thus somewhat similar to the splay tree.

23.1.1 merging is fundamental

If a heap-ordered, structurally unconstrained binary tree is used to represent a
priority queue, merging becomes the fundamental operation. This is because
we can perform other operations as follows:

h.insert( x ) : Create a one-node tree containing x and merge that tree
into the priority queue.

n

h.findMin( ) : Return the item at the root. n

h.deleteMin( ) : Delete the root and merge its left and right subtrees. n

h.decreaseKey( p, newVal ) : Assuming that p is a reference to a node
in the priority queue, we can lower p 's key value appropriately and
then detach p from its parent. Doing so yields two priority queues that
can be merged. Note that p (meaning the position) does not change as
a result of this operation (in contrast to the equivalent operation in a
binary heap).

n

The decreaseKey
operation is imple-
mented by detach-
ing a subtree from
its parent and then
using merge .

We need show only how to implement merging; the other operations
become trivial. The decreaseKey operation is important in some advanced
applications. We presented one illustration in Section 14.3—Dijkstra's algo-
rithm for shortest paths in a graph. We did not use the decreaseKey operation in
our implementation because of the complications of maintaining the position
of each item in the binary heap. In a merging heap, the position can be main-
tained as a reference to the tree node, and unlike in the binary heap, the posi-
tion never changes.
In this section we discuss one implementation of a mergeable priority
queue that uses a binary tree: the skew heap. First, we show that, if we are not
concerned with efficiency, merging two heap-ordered trees is easy. Next, we
cover a simple modification (the skew heap) that avoids the obvious ineffi-
ciencies in the original algorithm. Finally, we give a proof that the merge oper-
ation for skew heaps is logarithmic in an amortized sense and comment on the
practical significance of this result.

23.1.2 simplistic merging of heap-ordered trees

Let us assume that we have two heap-ordered trees, H 1 and H 2 , that need to be
merged. Clearly, if either of the two trees is empty, the other tree is the result
of the merge. Otherwise, to merge the two trees, we compare their roots. We

Two trees are easily
merged recursively.