Heap Representation Using Arrays

Because a Binary Heap is strictly a Complete Binary Tree with no missing left nodes, it can be mapped into a 1D flat array with zero pointer overhead.

The Coordinate Mapping Formulas

For a node stored at array index i (0-indexed):

Copy code              [ 0 ]
             /     \
         [ 1 ]     [ 2 ]
        /     \   /     \
     [ 3 ]  [ 4 ][ 5 ]  [ 6 ]

Calculation Example:

Consider node at index i = 1:

• Left child: 2(1) + 1 = 3
• Right child: 2(1) + 2 = 4
• Parent: floor((1 - 1) / 2) = 0

Sift-Up (Heapify-Up) Operation

When inserting a new value:

1. Append the new value at the end of the array (at size).
2. Sift it up: compare with its parent. If it violates the heap property, swap them. Repeat until the parent is valid or root is reached.

Copy codeprivate fun siftUp(index: Int) {
    var curr = index
    while (curr > 0) {
        val parent = (curr - 1) / 2
        if (heap[curr] < heap[parent]) { // Min-heap condition
            swap(curr, parent)
            curr = parent
        } else {
            break
        }
    }
}

Sift-Down (Heapify-Down) Operation

When extracting the root (min or max):

1. Replace the root with the last element in the array.
2. Decrement size.
3. Sift it down: compare with both children, swap with the smaller (in min-heap) child. Repeat until children are valid or a leaf is reached.

Copy codeprivate fun siftDown(index: Int) {
    var curr = index
    val size = heap.size
    while (2 * curr + 1 < size) {
        var smallest = 2 * curr + 1 // Left child
        val right = smallest + 1
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right
        }
        if (heap[smallest] < heap[curr]) {
            swap(curr, smallest)
            curr = smallest
        } else {
            break
        }
    }
}

Summary

• Arrays represent complete binary trees without pointers using: left = 2i + 1, right = 2i + 2, parent = (i - 1) / 2.
• Array representation delivers superb cache locality and compact memory storage.
• Insertion sifts up (O(log n)); extraction sifts down (O(log n)).