Page 230 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 11: Leftist Heaps and Binomial Queues

The expression for the running time for the insert operation follows directly from that of the Notes
merge operation. That is, the time required for the insert operation in the worst case is
(d – 1)τ(isGT) + O(d),
where d is the null path length of the heap into which the item is inserted. If you assume that two
keys can be compared in constant time, the running time for insert becomes simply O(log n),
where n is the number of nodes in the tree into which the item is inserted.

Task Discuss the use of enqueue method.

11.1.5 Removing items from a Leftist Heap

The fi ndMin method locates the item with the smallest key in a given priority queue and the
dequeueMin method removes it from the queue. Since the smallest item in a heap is found at the
root, the fi ndMin operation is easy to implement. Program 11.4 shows how it can be done. Clearly,
the running time of the fi ndMin operation is O(1).
public class LeftistHeap
extends BinaryTree
implements MergeablePriorityQueue
{
protected int nullPathLength;
public Comparable findMin ()
{
if (isEmpty ())
throw new ContainerEmptyExeception ();
return (Comparable) getKey ();
}
// ...
}
Program 11.4: LeftistHeap Class fi ndMin Method
Since the smallest item in a heap is at the root, the dequeueMin operation must delete the root
node. Since a leftist heap is a binary heap, the root has at most two children. In general when the
root is deleted, you are left with two non-empty leftist heaps. Since you already have an effi cient
way to merge leftist heaps, the solution is to simply merge the two children of the root to obtain a
single heap again! Program 11.5 shows how the dequeueMin operation of the LeftistHeap class
can be implemented.

public class LeflistHeap
extends BinaryTree
implements MergeablePriorityQueue
{
protected int nullPathLength;
public Comparable dequeueMin ()
{
if (isEmpty ())

LOVELY PROFESSIONAL UNIVERSITY 225