only (e)

1. (18 marks) Consider the following scenario. A set of machines are to process jobs of varying priorities. Each machine has it's own set of jobs stored in a priority queue. At times machines go down and we want to merge the priority queue of the down machine with one that is running. Once the dowin machine is up and running again, we'd like to split the priority queue of a machine to give the newly up and running machine a priority queue of jobs to complete. We will model this problem as special variation of a heap called a dangling-heap. A dangling-heap of height h is a tree consisting of a root with exactly one child, which is the root of a complete binary tree of the remaining 2h -1 nodes the root and (updated Feb. 14) and the complete binary tree satisfy a priority condition: the element at any node is the maximum of all the elements in the subtree rooted at that node (like a heap) . Note that a dangling-heap of height 0 consists of a single node. 4-for this question, things work out slightly more neatly with this definition of height Figure 1: The heap has 2h - 1 nodes, so the dangling-heap has 2h nodes A dangling-heap forest is a sequence of dangling-heaps Do, Di,.. . Dm such that height(Di-1)