Questions
14 of 26
What is Heapify? Explain the process.
Difficulty: 3/10
Heapify
Heapify is the process of restoring the heap-order property. For a node, we compare it with its children, select the appropriate child according to min-heap or max-heap ordering, swap when necessary, and continue downward. Bottom-up heap construction applies this process from the last non-leaf node toward the root and builds a heap in O(n) time.
javascript
- 1
Sift-down heapify for one node is O(log n).
- 2
Bottom-up construction of a heap is O(n).
- 3
Heapify does not mean sorting the array.
- 4
After heapify, the heap-order property is restored.
Follow-up Questions
- Why is bottom-up heap construction O(n), not O(n log n)?
- What is the difference between sift-up and sift-down?