Description
A pennant of height h is a tree consisting of 2h nodes: a root with exactly one child, which is
the root of a complete binary tree of the remaining 2h − 1 nodes. It also satisfies the max-heap
property: the element at any node has priority at least as big as all the elements in the subtree
rooted at that node. Note that a pennant of height 0 consists of a single node.
A pennant forest is a sequence of pennants P0, P1, . . . , Pm such that
• height(Pi−1) ≤ height(Pi), for 0 < i ≤ m.
• There are at most 2 pennants of any height.
• There are at least i + 1 pennants of height at most i, for 0 ≤ i ≤ m.
• There are at most i + 2 pennants of height at most i, for 0 ≤ i ≤ m.
• The element at the root of Pi−1 ≤ the element at the root of Pi
, for 0 < i ≤ m.
1. Prove that if P0, P1, . . . , Pm is a pennant forest, then it contains at least 2m nodes and fewer
than 2m+1 nodes.
2. Give an efficient algorithm that, given a max-heap of height h, constructs a pennant forest
P0, . . . , Ph with the same elements.
3. Give an efficient algorithm that, given a pennant forest P0, . . . , Pm, constructs a max-heap of
height m with the same elements.
4. Give an efficient algorithm for splitting a pennant of height h into two pennants of height
h − 1.
5. Give an efficient algorithm for merging two pennants of height h − 1 into a pennant of height
h.
6. Give an algorithm that takes a sequence P0, . . . , Pm of pennants that satisfies the first four
properties of a pennant forest and constructs a pennant forest with the same nodes. Your
algorithm should run in O(m2
) time.
Explain why your algorithms are correct and run in the required times.
1
