11.4. Heaps as a Sorting Algorithm

Try these first

1. 1.

   What type of heap has the maximum element at the root?

   Hint

   Think about which is at the highest priority.

2. 2.

   Describe what happens during the delete max operation.

   Hint

   Consider how the structure needs to be maintained.

3. 3.

   What is the time complexity of heapsort?

   • O(n)
   • O(n log n)
   • O(log n)

   Hint

   Think about both building and extracting complexities.

4. 4.

   True or False: A min-heap ensures the maximum element is at the root.

   • True
   • False

   Hint

   Remember the definitions of heap types!

5. 5.

   Design an algorithm to construct a max-heap from an unsorted array of integers. Show intermediate steps.

   Hint

   Consider each subtree and how to ensure the heap property is maintained.

6. 6.

   Explain in detail how heapsort can be applied to sort an array of negative numbers.

   Hint

   Remember that sorting depends on order, not value sign.