10.2.2. Restoring Heap Property

Try these first

1. 1.

   What is the maximum element in a max heap?

   Hint

   Where does the largest value always sit in a max heap?

2. 2.

   What do we call the process of moving a node down to restore the heap?

   Hint

   Think about what term describes going downward in the structure.

3. 3.

   Where is the maximum value located in a max heap?

   • At the left child
   • At the right child
   • At the root

   Hint

   Consider which node is at the top of the heap.

4. 4.

   True or False: The height of a heap is linear with respect to the number of elements.

   • True
   • False

   Hint

   Reflect on the relationship between a complete tree structure and its height.

5. 5.

   Given a max heap with elements [20, 15, 10, 8, 7, 3], describe the step-by-step process of removing the maximum and restoring the heap.

   Hint

   Take each child comparison step and consider swapping based on their values.

6. 6.

   Construct a max heap from the following unsorted array: [5, 3, 8, 4, 1, 10]. Use bottom-up heapification to describe your steps.

   Hint

   Look at when the last non-leaf node starts fixing nodes above and the final height adjustments to maintain the structure.