============================================================================== CSC 263 Tutorial 2 Winter 2019 ============================================================================== (1) Alice claims that the *minimum* element of a binary max-heap must be one of its leaf nodes. Do you agree? Prove or disprove it. (2) Bob claims that the *median* element of a binary max-heap must be one of its leaf nodes. Do you agree? Prove or disprove it. (3) A ternary max-heap is like a binary max-heap except that non-leaf nodes have three children instead of two children. (As with binary heaps, there can of course be one non-leaf node that has fewer than three children.) We refer to the children as the left child, middle child, and right child. The values stored in the nodes are ordered according to the same principle as for binary max-heaps: the value at each node is greater than or equal to the values in the node’s children. Answer the following questions regarding ternary max-heaps. (a) Similar to binary heaps, a ternary heap is represented by an array. Given the index i of an element in the array, what are the indices of the left child, the middle child, the right child, and the parent of the element? Assume that the array index starts at 0. Be thorough and discuss all possible corner cases. (b) How do EXTRACT-MAX and INSERT work for a ternary max-heap? Explain their differences from the corresponding operations for binary max-heaps. No pseudo-code required. (c) Consider a function IS-TERNARY-MAX-HEAP(A) that takes an array A as the input and returns TRUE if and only if A represents a valid ternary max-heap. Write the pseudo-code of a recursive implementation (i.e., no loops) of IS-TERNARY-MAX-HEAP. Briefly explain (not a proof) the correctness of your pseudo-code and give an asymptotic upper-bound (big-Oh) on the worst-case runtime of your pseudo-code. (d) Write the pseudo-code of a iterative implementation (i.e., no recursion) of IS-TERNARY-MAX-HEAP. Briefly explain (not a proof) the correctness of your pseudo-code and give an asymptotic upper-bound (big-Oh) on the worst-case runtime of your pseudo-code.