10.5.2. Types of Heaps

Try these first

1. 1.

   Describe the main difference between max heaps and min heaps.

   Hint

   Think about the relationship between parent and child nodes.

2. 2.

   What time complexity does inserting an element in a heap have?

   Hint

   Consider the height of the heap and how far you might need to move elements.

3. 3.

   In a max heap, which of the following statements is true?

   • The largest element is always the leaf.
   • The largest element is always the root.
   • The largest element can be found anywhere.

   Hint

   Think about the structure of the heap.

4. 4.

   True or False: In a min heap, the children of a node can exceed the parent value.

   • True
   • False

   Hint

   Consider the definition of a min heap.

5. 5.

   Construct a max heap from the following array: [3, 9, 2, 15, 5, 11]. Illustrate the process.

   Hint

   Begin at the first non-leaf node, observe each parent-child relationship.

6. 6.

   Given a binary tree, how do you convert it to a min heap while preserving the tree's structure? Provide a step-by-step algorithm.

   Hint

   Think about how to organize the values layer by layer similar to level order traversal.