11.2.3. Handling Value Changes

Try these first

1. 1.

   What is a heap?

   Hint

   Think about the parent-child relationship.

2. 2.

   How do we restore the heap property when increasing a value?

   Hint

   Consider how values move in relation to their parent.

3. 3.

   What happens when a value in the heap is increased?

   • It stays the same
   • It bubbles down
   • It bubbles up

   Hint

   Think about how increasing a value affects its position.

4. 4.

   True or False: Dual arrays are used to keep track of vertex indices in heaps.

   • True
   • False

   Hint

   Consider the purpose of having two mapping arrays.

5. 5.

   You have a max-heap with the values [50, 30, 20, 15, 10, 8, 5]. If you insert 40 and then decrease it to 25, describe the steps taken to maintain the heap property.

   Hint

   Focus on both insertion and value modification through bubbling.

6. 6.

   Write a complete algorithm to handle a value increase in a min-heap, including handling swaps up the tree.

   Hint

   Consider all the conditions where swaps will need to happen.