Harvard University Heaps Programming Worksheet

Question 5: Heaps(a) Suppose that we would like to verify if the elements in array A satisfy the heap property, assuming
the usual heap implementation shown in class. Write the pseudo-code for a recursive algorithm called
VerifyHeap(A), which returns true if A is indeed a valid max-heap, and false otherwise. You may use the
attribute A.heapsize. Write the recurrence for the runtime of your algorithm, and justify the worst-case
runtime of O(n) and the best-case of O(1).
7
(b) A max-heap is contained in array A, using the implementation as shown in class. However, the
array contains an error, in that the entry at index k is empty. Instead of rebuilding the entire heap from
scratch, design an algorithm that repairs the heap. The result of your algorithm must contain a valid heap
in array A with a correct A.heapsize attribute. Write the pseudo-code for your algorithm, which must be
called Repair Heap(A,k). Justify the worst-case runtime of O(log n) and the best-case of O(1).
(c) At the 2020 Tokyo Olympics, there are n athletes competing in the 100m sprint. The organizers
have planned for exactly 5 heats, with each heat containing n/5 athletes. The finish times of each heat will
be stored in a min-heap: H1, H2, H3, H4, H5. For example, H1 is a min-heap containing the finish times
of the athletes from the first heat. Once the heats are complete, the organizers must determine the top 40
athletes who will continue to the quarter-finals. Design an algorithm that takes as input the five heaps,
and outputs the best 40 finish times, over all athletes, regardless of heat. Call your algorithm Top40(H1,
H2, H3, H4, H5) and provide the pseudo-code. Justify the runtime of O(log n).