Priority Queue Homework

Priority Queue Homework#

Question 1#

Start with the following min-heap, represented as an array: [3, 5, 10, 8, 7, 11, 15, 12, 9].

(a) Draw the heap as a tree.

(b) Perform the following operations, and write the state of the array after each subsequent function call.

  • insert (4)

  • insert (2)

  • removeMin()

Question 2#

You will perform an in-place heap sort on the following array: [4, 10, 8, 5, 1, 12, 9]. Remember: In-place heap sort uses a max-heap.

(a) Bottom-Up Heapify: Show the final state of the array after the bottom-up heap construction (heapify) algorithm is complete.

(b) Sort-Down Phase: Starting from your max-heap in Q1, show the final state of the array after the first two iterations of the “Sort-Down” phase (i.e., after the two largest elements are in their final sorted positions).