A heap is a binary tree where each node stores a priority, and in which every node satisfies the heap property: the priority of a node u must be greater than or equal to the priorities of the roots of both of u’s subtrees. (The restriction only applies for a subtree that is not null.)
1. Give a recursive definition of a heap.
2. Prove by structural induction that every heap is empty, or that no element of the heap is larger than its root node. (That is, the root is a maximum element.)
3. Prove by structural induction that every heap is empty, or it has a leaf u such that u is no larger than any node in the heap. (That is, the leaf u is a minimum element.)
A 2–3 tree is a data structure, similar in spirit to a binary search tree (see Exercise 5.83)—or, more precisely, a balanced form of BST, which is guaranteed to support fast operations like insertions, lookups, and deletions. The name “2–3 tree” comes from the fact that each internal node in the tree must have precisely 2 or 3 children; no node has a single child. Furthermore, all leaves in a 2–3 tree must be at the same “level” of the tree