10.3.1. Array Representation of Heap

Try these first

1. 1.

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

   Hint

   Think about the levels you need to traverse.

2. 2.

   In a max heap, which node is the largest?

   Hint

   Consider the properties of a max heap.

3. 3.

   What is the maximum height of a heap with n elements?

   • O(n)
   • O(log n)
   • O(n log n)

   Hint

   Remember how the tree structure expands.

4. 4.

   True or False: In a min heap, the maximum value is always found at the root.

   • True
   • False

   Hint

   Reflect on the properties of min vs max heaps.

5. 5.

   Given a randomly ordered array of ten numbers, describe and illustrate how you would transform it into a max heap using the bottom-up method.

   Hint

   Focus on how each subtree adheres to the max heap property while going up.

6. 6.

   If you start with a max heap of size n and repeatedly remove elements, how does the structure change?

   Hint

   Visualize how nodes maintain balance and fill gaps after each removal.