19-4 2-3-4 heaps

Chapter 18 introduced the 2-3-4 tree, in which every internal node (other than possibly the root) has two, three, or four children and all leaves have the same depth. In this problem, we shall implement 2-3-4 heaps, which support the mergeable-heap operations.

The 2-3-4 heaps differ from 2-3-4 trees in the following ways. In 2-3-4 heaps, only leaves store keys, and each leaf $x$ stores exactly one key in the attribute $x.key$. The keys in the leaves may appear in any order. Each internal node $x$ contains a value $x.small$ that is equal to the smallest key stored in any leaf in the subtree rooted at $x$. The root $r$ contains an attribute $r.height$ that gives the height of the tree. Finally, 2-3-4 heaps are designed to be kept in main memory, so that disk reads and writes are not needed.

Implement the following 2-3-4 heap operations. In parts (a)–(e), each operation should run in $O(\lg n)$ time on a 2-3-4 heap with $n$ elements. The $\text{UNION}$ operation in part (f) should run in $O(\lg n)$ time, where $n$ is the number of elements in the two input heaps.

a. $\text{MINIMUM}$, which returns a pointer to the leaf with the smallest key.

b. $\text{DECREASE-KEY}$, which decreases the key of a given leaf $x$ to a given value $k \le x.key$.

c. $\text{INSERT}$, which inserts leaf $x$ with key $k$.

d. $\text{DELETE}$, which deletes a given leaf $x$.

e. $\text{EXTRACT-MIN}$, which extracts the leaf with the smallest key.

f. $\text{UNION}$, which unites two 2-3-4 heaps, returning a single 2-3-4 heap and destroying the input heaps.

a. Traverse a path from root to leaf as follows: At a given node, examine the attribute $x.small$ in each child-node of the current node. Proceed to the child node which minimizes this attribute. If the children of the current node are leaves, then simply return a pointer to the child node with smallest key. Since the height of the tree is $O(\lg n)$ and the number of children of any node is at most $4$, this has runtime $O(\lg n)$.

b. Decrease the key of $x$, then traverse the simple path from $x$ to the root by following the parent pointers. At each node $y$ encountered, check the attribute $y.small$. If $k < y.small$, set $y.small = k$. Otherwise do nothing and continue on the path.

c. Insert works the same as in a B-tree, except that at each node it is assumed that the node to be inserted is 'smaller' than every key stored at that node, so the runtime is inherited. If the root is split, we update the height of the tree. When we reach the final node before the leaves, simply insert the new node as the leftmost child of that node.

d. As with $\text{B-TREE-DELETE}$, we'll want to ensure that the tree satisfies the properties of being a 2-3-4 tree after deletion, so we'll need to check that we're never deleting a leaf which only has a single sibling. This is handled in much the same way as in chapter 18. We can imagine that dummy keys are stored in all the internal nodes, and carry out the deletion process in exactly the same way as done in exercise 18.3-2, with the added requirement that we update the height stored in the root if we merge the root with its child nodes.

e. $\text{EXTRACT-MIN}$ simply locates the minimum as done in part (a), then deletes it as in part (d).

f. This can be done by implementing the join operation, as in Problem 18-2 (b).