11.4.1. Building and Maintaining a Heap

Try these first

1. 1.

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

   Hint

   Think about the height of the tree.

2. 2.

   What is a min-heap?

   Hint

   Consider how it relates to priority.

3. 3.

   What is the primary purpose of a heap data structure?

   • To sort elements
   • To manage priority queues
   • To store arrays

   Hint

   Consider what ‘priority’ means.

4. 4.

   True or False: In a min-heap, the root node is always the largest.

   • True
   • False

   Hint

   Reflect on the nature of min vs max.

5. 5.

   Given a scenario where elements are inserted into a min-heap, describe how to construct the heap step by step. Start with the array [5, 3, 8, 4, 1]. Illustrate each insertion and the resultant heap after each step.

   Hint

   Think about how parents and children relate in value when inserting.

6. 6.

   Imagine you have a min-heap structured as [2, 3, 5, 7, 9] and you want to decrease the value of 5 to 1. Explain the steps required to maintain the integrity of the heap structure after this operation.

   Hint

   What happens first when you change a value?