(a)

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 down 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 va riation of a heap called a dangling-heap A dangling-heap 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 e 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. 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 height(D), for 0