11.2.2. Updating Heap Values

Try these first

1. 1.

   What time complexity do heaps allow for insertions?

   Hint

   Think about the structure of a heap.

2. 2.

   In a max-heap, how must the values relate between parent and child nodes?

   Hint

   Consider how heaps are structured.

3. 3.

   What is the primary property of a max-heap?

   • A: Parent nodes are smaller than their children
   • B: Parent nodes are larger than their children
   • C: Parent nodes and children are equal

   Hint

   Visualize a heap.

4. 4.

   Dijkstra’s Algorithm requires how long to update the values in a heap?

   • True
   • False

   Hint

   Consider the time complexities related to heaps.

5. 5.

   Given a min-heap with the values [4, 10, 8, 20, 15], what is the structure of this heap after deleting the minimum value? Illustrate the heaps before and after the deletion.

   Hint

   Always replace the root with a leaf and rebalance.

6. 6.

   Consider a situation in Dijkstra’s algorithm where you need to update a vertex's distance. Describe the steps required to identify and adjust the heap accordingly.

   Hint

   It's about tracking where the changes need to occur.