10.5. Heap Operations Summary

Try these first

1. 1.

   What is a max-heap?

   Hint

   Think about the root node in a max-heap.

2. 2.

   What is the time complexity of inserting an element in a heap?

   Hint

   Consider the height of the heap.

3. 3.

   What is the time complexity of both insertion and deletion in a max-heap?

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

   Hint

   Think about the height of a binary tree as you determine time complexity.

4. 4.

   A min-heap requires that every parent node be larger than its children.

   • True
   • False

   Hint

   Consider the definition of a min-heap.

5. 5.

   Explain how the time complexity of the heapifying process leads to an overall O(N) time complexity when constructing a heap from an unordered array.

   Hint

   Focus on how node counts decrease while fixing the heap properties.

6. 6.

   Take an array of numbers and transform it into a max-heap. Outline each step you take in the process.

   Hint

   Recall the definition of a max-heap while performing swaps.