An array-based implementation of priority queues is not ideal if we often need to merge several priority queues into one, or if we are programming in a language that does not have arrays. Here we are interested in a data structure that is adaptive and supports efficient merging, by which we mean taking two priority queues P and P and forming a new priority queue with elements P P . As is often the case with adaptive data structures, some operations may be worst-case expensive, but when we average their cost across many applications, they are cheap. That will be the case for the operations we want to implement here: Merge, Insert, and DeleteMax; all can be made to have O(log n) worst-case behaviour, amortised. Your task is to reconstruct pseudo-code for the three operations (including some helper functions). The appendix contains a scrambled solution, with lines of pseudo-code in random order, without any indentation. You are asked to reconstruct the original code, with proper indentation. The data structure we use is a kind of multiway tree, that is, a node can have any number of subtrees. Since it is a multiway tree and also a (max-)heap, we will call it a meap. A meap M can be empty, in which case we denote it void. If M is non-empty then M has a key, plus a list of non-empty sub-trees (sub-meaps). Note that the list of subtrees can be of any length; in particular it can be empty. A tree list L can be empty, in which case we denote it null. If L is non-empty, then L has a first tree, L.elt and a tail, L.next, with the remaining trees. In our case, these trees are all meaps. A meap M (other than void) has two attributes: M.key is the root nodes key. M.subtrees is a tree listthe list of Ms sub-meaps. A meap must satisfy the heap condition: The key of a child node is smaller than the key of its parent. That is, for every meap M in M.subtrees, we have M .key M.key. The heap condition must hold recursively, for all nodes. Below are two meaps, M1 (on the left) and M2 (on the right): 92 75 16 52 27 33 66 44 49 7 10 81 30 64 57 23 44 Here M1.key = 92 and M1.subtrees is a list of five children. These children are meaps with roots 75, 33, 66, 49, and 10. To find and return the largest key in a meap is easyit is just the roots key; we will not be worried about that operation in this question. To merge two meaps, we include the meap that has the smaller root key as the leftmost subtree of the other meap. Merging the two meaps above, we get Merge(M1, M2), shown here: 92 81 30 64 57 23 44 75 16 52 27 33 66 44 49 7 10 Once Merge has been implemented, Insert is easy. DeleteMax removes the largest element from a meap. It also makes use of Merge but is more complicated. After discarding the root it must merge the children, to return a single meap. We do the merging in two passes. First we merge the children in pairs from left to right (that is, the first child with the second, the third with the fourth, and so on). Then we merge the resulting meaps in a single sweep from right to left. Continuing our example, removal of the root (92) leaves us with six meaps to merge: 81 30 64 57 23 44 75 16 52 27 33 66 44 49 7 10 Merging pairwise, from left to right, we get: 81 75 16 52 27 30 64 57 23 44 66 33 44 49 10 7 Now, merging the resulting meaps in a single pass from right to left, we get: 81 66 49 10 7 33 44 75 16 52 27 30 64 57 23 44 Now have fun re-assembling the code from the appendix.