2-3-4 heaps Chapter 18 introduced the 2-3-4 tree, in which

Chapter 19, Problem 19-4

(choose chapter or problem)

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 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. MINIMUM, which returns a pointer to the leaf with the smallest key. b. DECREASE-KEY, which decreases the key of a given leaf x to a given value k x:key. c. INSERT, which inserts leaf x with key k. d. DELETE, which deletes a given leaf x. e. EXTRACT-MIN, which extracts the leaf with the smallest key. f. UNION, which unites two 2-3-4 heaps, returning a single 2-3-4 heap and destroying the input heaps.