Page 231 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes throw new ContainerEmptyException ();
Comparable result = (Comparable) getKey ();
LeftistHeap oldLeft = getLeftHeap ();
LeftistHeap oldRight = getRightHeap ();
purge ();
swapContents (oldLeft);
merge (oldRight);
return result;
}
// ...
}
Program 11.5: LeftistHeap Class dequeueMin Method
The running time of Program 11.5 is determined by the time required to merge the two children of
the root (line 17) since the rest of the work in dequeueMin can be done in constant time. Consider
the running time to delete the root of a leftist heap T with n internal nodes. The running time to
merge the left and right subtrees of T
(d – 1 + d – 1)τ(isGT) + O(d + d ),
L R L R
where d and d are the null path lengths of the left and right subtrees T, respectively. In the worst
L
R
case, d = 0 and d = ⎣log n⎦.
R L 2
11.2 Skew Heaps

There are several ways to implement heaps in a self-adjusting fashion. The one I shall discuss is
called skew heaps as proposed by Sleator and Tarjan, and is analogous to leftist heaps. A skew
heap is a heap-ordered binary tree. That is, it is a binary tree with one key in each node so that
for each node x other that the root, the key at node x is no less than the key at the parent of x. To
represent such a tree you store in each node x its associated key, denoted key(x) and two pointers
left(x) and right(x), to its left child and right child, respectively. If x has no left child I defi ne
left(x) =L; if x has no right child I define right(x) =L. Access to the tree is by a pointer to its root;

you represent an empty tree by a pointer to L.
With this representation you can carry out the various heap operations as follows. I perform
makeheap(h) in O(1) time by initializing h to L. Since heap order implies that the root is a

minimum key in the tree, you can carry out findmin(h) in O(1) time by returning the key at the
root; returning null if the heap is empty. You perform insert and deletemin using union. To carry
out insert(k , h), I make k into a one-node heap and Union it with h. To carry out deletemin(h),
if h is not empty I replace h by the Union of its left and right subtrees and return the key at the
original root. (If h is originally empty you return null.)
To perform union( h1 , h2), you form a single tree by traversing down the right paths of h1 and
h2, merging them into a single right path with keys in nondecreasing order. First assume the left
subtrees of nodes along the merge path do not change. (Figure 11.3(a).) The time for the Union
operation is bounded by a constant times the length of the merge path. To make Union effi cient,
you must keep right paths short. In leftist heaps this is done by maintaining the invariant that,
for any node x, the right path descending from x is a shortest path down to a missing node.
Maintaining this invariant requires storing at every node the length of a shortest path down
to a missing node; after the merge you walk back up the merge path, updating the shortest
path lengths and swapping left and right children as necessary to maintain the leftist property.
The length of the right path in a leftist heap of n nodes is at most log n, implying an O( log n)

226 LOVELY PROFESSIONAL UNIVERSITY