10.1.2. Insert Operation Complexity

Try these first

1. 1.

   What is the time complexity of insert operations in heaps?

   Hint

   Think about what governs the height of the tree.

2. 2.

   Where is the maximum element found in a max-heap?

   Hint

   Is it at the top or somewhere deeper in the tree?

3. 3.

   What is the time complexity of inserting into a heap?

   • O(N)
   • O(log N)
   • O(N^2)

   Hint

   Consider how many levels we might have in a tree with N elements.

4. 4.

   True or False? The maximum value in a max-heap can be found at any leaf node.

   • True
   • False

   Hint

   Recall the definition of a max-heap.

5. 5.

   Given an initial heap [50, 30, 20, 10], how would the heap look after inserting 40? Show the intermediate steps.

   Hint

   Consider how to keep the parent node greater than its children.

6. 6.

   If you start with a heap of [45, 30, 20, 10] and perform a delete max operation, what will the sequence of heaps look like? Describe each removal step.

   Hint

   Focus on restoring the heap property after each deletion.