11.3. Complexity Analysis

Try these first

1. 1.

   What data structure does a heap represent?

   Hint

   Think about the structure that allows maximum or minimum retrieval efficiently.

2. 2.

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

   Hint

   Consider the height of the tree.

3. 3.

   What is the time complexity of deleting the maximum element from a min-heap?

   • O(N)
   • O(log N)
   • O(1)

   Hint

   Think about the structure's height.

4. 4.

   Dijkstra's algorithm finds the shortest path using which data structure?

   • True
   • False

   Hint

   Recall how we discussed the algorithm's functionality.

5. 5.

   Explain how you would implement Dijkstra's algorithm without using a heap. What would be the time complexity?

   Hint

   Consider the implications of not having logarithmic retrieval.

6. 6.

   Describe an application where heaps and their sorting could greatly enhance efficiency.

   Hint

   Think about systems that require quick access to priorities, like CPU scheduling.