Visualization Exercise: Heap Tree Construction

Building a heap from an arbitrary array can be done naively in O(n log n) time by inserting elements one by one. However, Floyd's buildHeap() algorithm does it in O(n) linear time!

Floyd's Bottom-Up buildHeap() in O(n)

Instead of inserting from top to bottom, buildHeap() sifts down from the last internal node up to the root:

• In a complete tree of size N, all leaf nodes are already trivial 1-element heaps!
• Leaf nodes span from index floor(N / 2) to N - 1.
• We only need to run siftDown() on indices from floor(N / 2) - 1 down to 0!

Copy codefun buildMaxHeap(arr: IntArray) {
    val n = arr.size
    // Start at last non-leaf node
    for (i in (n / 2 - 1) downTo 0) {
        siftDown(arr, n, i)
    }
}

Manual Trace Example

Convert unsorted array: [ 4, 10, 3, 5, 1 ] into a Max-Heap.

• Size N = 5
• Last non-leaf node: index floor(5 / 2) - 1 = 1 (value 10).

Copy codeInitial Tree:
         [ 4 ]
        /     \
     [ 10 ]   [ 3 ]
     /    \
   [ 5 ]  [ 1 ]

Step 1: Sift-Down index 1 (value 10)

• Children of 10 are 5 and 1.
• 10 is already greater than both → No change.

Step 2: Sift-Down index 0 (value 4)

• Children of 4 are 10 (index 1) and 3 (index 2).
• Largest child is 10.
• Swap 4 and 10!

Copy codeAfter Swap:
         [ 10 ]
        /      \
     [ 4 ]    [ 3 ]
     /   \
   [ 5 ] [ 1 ]

• Continue sifting down 4:
  • Children of 4 are 5 (index 3) and 1 (index 4).
  • Largest child is 5.
  • Swap 4 and 5!

Copy codeFinal Max-Heap:
         [ 10 ]
        /      \
     [ 5 ]    [ 3 ]
     /   \
   [ 4 ] [ 1 ]

Array: [ 10, 5, 3, 4, 1 ]

Every parent is now greater than its children in just 2 swaps!

Summary

• Building a heap bottom-up runs in O(n) linear time by ignoring leaves and sifting down from index (N/2 - 1) to 0.
• In-place heap construction powers Heapsort without requiring extra memory allocation.