Page 236 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 11: Leftist Heaps and Binomial Queues

11.4 Summary Notes

A power-of-2 heap is a left-heap-ordered tree consisting of a root node with an empty right
subtree and a complete left subtree.
The tree corresponding to a power-of-2 heap by the left-child, right-sibling correspondence
is called a binomial tree.
Binomial trees and power-of-2 heaps are equivalent. I work with both representations
because binomial trees are slightly easier to visualize, whereas the simple representation of
power-of-2 heaps leads to simpler implementations.

11.5 Keywords

Binomial Queue: A binomial queue is a priority queue that is implemented not as a single tree
but as a collection of heap-ordered trees.

Leftist Heap: A leftist heap is a heap-ordered binary tree which has a very special shape called
a leftist tree.
Leftist Tree: A leftist tree is a tree which tends to ``lean’’ to the left. The tendency to lean to the left
is defined in terms of the shortest path from the root to an external node.

Skew Heap: A skew heap is a heap-ordered binary tree.

11.6 Self Assessment

Fill in the blanks:
1. A collection of trees is called a ........................ .

2. Every node in binary tree has associated with it a quantity called its ........................ .
3. The null path length of an empty tree is ........................ .
4. A leftist tree is a tree in which the shortest path to an external node is always on the
........................ .
5. The ........................ method of the LeftistHeap class is used to put items into the heap.
6. The ........................ method locates the item with the smallest key in a given priority
queue.

7. Skew heaps as proposed by ........................ .
8. Each of the trees in a binomial queue has a very special shape called a ........................ .

11.7 Review Questions

1. What do you mean by leftist heaps?
2. Describe null path and null path length.

3. Write the methods to implement queues by the simple but slow technique of keeping the

front of the queue always in the first position of a linear array.
4. Prove that “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)⎦
2
nodes.”

LOVELY PROFESSIONAL UNIVERSITY 231