9.4. Insertion and Deletion in Heaps

Try these first

1. 1.

   What is the maximum value of a max-heap?

   Hint

   Look at the root of the tree.

2. 2.

   Describe how to insert a new value into a heap.

   Hint

   What position do we fill when adding a new node?

3. 3.

   What property must a max-heap satisfy?

   • A. Every parent node must be less than its children.
   • B. Every parent node must be equal to its children.
   • C. Every parent node must be greater than or equal to its children.

   Hint

   Think about the definition of max-heap.

4. 4.

   True or False: Insertion in a heap can violate the max-heap property.

   • True
   • False

   Hint

   What happens when we add a value larger than its parent?

5. 5.

   Given a max-heap of [30, 20, 25], insert 15 and demonstrate the steps required to maintain the heap property.

   Hint

   Where does 15 go, and does it change anything?

6. 6.

   Starting with the heap [50, 30, 25, 20, 15], delete the root and show the new state of the heap after replacement and sifting down.

   Hint

   Ensure to visualize each change step.