How does a binary heap work, and how can a simple array represent it without node pointers, including Heapify?

Short answer

A binary heap is a nearly complete binary tree that satisfies the heap property (in a Min-Heap each parent is smaller than its children; in a Max-Heap it is larger). It is efficiently represented as an array where the children of index i are at 2i+1 and 2i+2.

Explanation

Because the tree is always complete, pointers are unnecessary: a node at index i has a left child at 2*i + 1, a right child at 2*i + 2, and a parent at floor((i-1)/2). Heapify converts an arbitrary array into a heap in linear O(N) time instead of O(N log N) by building levels bottom-up; extracting the root takes O(log N).

Code example

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:      # sift up: parent = (i - 1) // 2
            a[(i - 1) // 2], a[i] = a[i], a[(i - 1) // 2]
            i = (i - 1) // 2

    def pop(self):
        a = self.a
        a[0], a[-1] = a[-1], a[0]
        top = a.pop()
        i = 0
        while True:                                   # sift down (heapify): children = 2i+1, 2i+2
            left, right, smallest = 2 * i + 1, 2 * i + 2, i
            if left < len(a) and a[left] < a[smallest]:
                smallest = left
            if right < len(a) and a[right] < a[smallest]:
                smallest = right
            if smallest == i:
                return top
            a[smallest], a[i] = a[i], a[smallest]
            i = smallest

Common mistakes

• Confusing a binary search tree (BST) with a binary heap: a heap does not order left and right children relative to one another, only relative to their parent.

Follow-up questions

• What is the fundamental difference between Stack Memory and Heap Memory for program resource management?

Sources

• Binary heap - Wikipedia