Page 226 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 11: Leftist Heaps and Binomial Queues

Figure 11.1: A Leftist Heap Notes

The reason for our interest in leftist trees is illustrated by the following theorems:

Theorem-11.1

Consider a leftist tree T which contains n internal nodes. The path leading from the root of T
downwards to the rightmost external node contains at most ⎣log (n + 1)⎦ nodes.
2
extbfProof Assume that T has null path length d. Then T must contain at least 2 leaves.
d–1
Otherwise, there would be a shorter path than d from the root of T to an external node.
A binary tree with exactly l leaves has exactly l-1 non-leaf internal nodes. Since T has at least 2
d–1
leaves, it must contain at least n ≥ 2 – 1 internal nodes altogether. Therefore, d ≤ log (n + 1).
d
2
Since T is a leftist tree, the shortest path to an external node must be the path on the right. Thus,
the length of the path to the rightmost external is at most ⎣log (n + 1)⎦.
2
There is an interesting dichotomy between AVL balanced trees and leftist trees. The shape of an
AVL tree satisfies the AVL balance condition which stipulates that the difference in the heights of

the left and right subtrees of every node may differ by at most one. The effect of AVL balancing
is to ensure that the height of the tree is O(log n).
On the other hand, leftist trees have an ``imbalance condition’’ which requires the null path
length of the left subtree to be greater than or equal to that of the right subtree. The effect of the
condition is to ensure that the length of the right path in a leftist tree is O(log n).

Therefore, by devising algorithms for manipulating leftist heaps which only follow the right path
of the heap, you can achieve running times which are logarithmic in the number of nodes.
The dichotomy also extends to the structure of the algorithms. For example, an imbalance

sometimes results from an insertion in an AVL tree. The imbalance is rectified by doing rotations.
Similarly, an insertion into a leftist tree may result in a violation of the ``imbalance condition.’’
That is, the null path length of the right subtree of a node my become greater than that of the left
subtree. Fortunately, it is possible to restore the proper condition simply by swapping the left
and right subtrees of that node.
11.1.2 Implementation

This section presents an implementation of leftist heaps that is based on the binary tree
implementation. Program 11.1 introduces the LeftistHeap class. The LeftistHeap class extends
the BinaryTree class introduced in Program 11.1 and it implements the MergeablePriorityQueue

interface defined in Program 11.1.

LOVELY PROFESSIONAL UNIVERSITY 221