Page 229 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes where τ(isGT) is time required to compare two keys. If you assume that the time to compare two
keys is a constant, then you get O(log n + log n ), where n and n are the number of internal
2
1
2
1
nodes in trees T and T , respectively.
1 2
public class LeftistHeap
extends BinaryTree
implements MergeablePriorityQueue
{
protected int nullPathLength;
public void merge (MergeablePriorityQueue queue)
{
LeflistHeap arg = (LeftistHeap) queue;
if (isEmpty ())
swapContents (arg);
else if (!arg.isEmpty ())
{
if (((Comparable) getKey ()).isGT (
((Comparable) arg.getKey ())) )
swapContents (arg);
getRightHeap ().merge (arg);
if (getLeftHeap ().nullPathLength <
getRightHeap ().nullPathLength)
swapSubtrees ();
nullPathLength = 1 + Math.min (
getLeftHeap ().nullPathLength,
getRightHeap ().nullPathLength);
}
}
// ...
}

Program 11.2: LeftistHeap Class merge Method

11.1.4 Putting items into a Leftist Heap

The enqueue method of the LeftistHeap class is used to put items into the heap. enqueue is
easily implemented using the merge operation. That is, to enqueue an item in a given heap, I
simply create a new heap containing the one item to be enqueued and merge it with the given
heap. The algorithm to do this is shown in Program 11.3.

public class LeflistHeap
extends BinaryTree
implements MergeablePriorityQueue
{
protected int nullPathLength;
public void enqueue (Comparable object)
{ merge (new LeflistHeap (object)); }
// ...
}

Program 11.3: LeftistHeap Class enqueue Method

224 LOVELY PROFESSIONAL UNIVERSITY