11.1.1. Heaps and Dijkstra's Algorithm

Try these first

1. 1.

   What is the time complexity of inserting an element into a heap?

   Hint

   Think about how many levels the tree has.

2. 2.

   Explain what a min heap is.

   Hint

   Consider the size relationship between parents and children.

3. 3.

   What does a min heap do?

   • Ensures parents are larger than children
   • Ensures parents are smaller than children
   • Does not impose any structure

   Hint

   Think of how hierarchy is maintained in a tree.

4. 4.

   Is Dijkstra's algorithm efficient for finding the shortest path in unweighted graphs?

   • True
   • False

   Hint

   Consider when each vertex is equally accessible.

5. 5.

   Implement a function that builds a min heap from a given array and demonstrate extraction of the minimum element.

   Hint

   Remember to percolate the elements down correctly after extraction.

6. 6.

   Design an example graph and apply Dijkstra's algorithm step by step, illustrating the heap updates and distance calculations.

   Hint

   Track the distances and the vertices as you proceed!