==============================================================================
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.