Heap Operations: Insert, Extract & Build-Heap

Every heap rests on two repair routines: sift-up (also called bubble-up) and sift-down (bubble-down). After any change, exactly one of them restores the heap property. Insert appends then sifts up; extract removes the root then sifts down; build-heap sifts down across the whole array. Master these three and you’ve mastered heaps. The examples below build a min-heap on top of the array layout from the binary heap.

Insert: append, then sift up

To add a value, place it at the end of the array (keeping the tree complete), then repeatedly swap it with its parent while it is smaller than that parent. It rises until it finds a parent that is no larger than it — or reaches the root. Since the tree height is log n, this is O(log n).

void siftUp(std::vector<int>& a, int i) {
    while (i > 0) {
        int p = (i - 1) / 2;
        if (a[i] >= a[p]) break;     // parent is smaller-or-equal: done
        std::swap(a[i], a[p]);
        i = p;
    }
}
void insert(std::vector<int>& a, int x) {
    a.push_back(x);                  // append at the end
    siftUp(a, (int)a.size() - 1);
}

void siftUp(List<Integer> a, int i) {
    while (i > 0) {
        int p = (i - 1) / 2;
        if (a.get(i) >= a.get(p)) break;        // parent smaller-or-equal
        Collections.swap(a, i, p);
        i = p;
    }
}
void insert(List<Integer> a, int x) {
    a.add(x);                                   // append at the end
    siftUp(a, a.size() - 1);
}

function siftUp(a, i) {
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (a[i] >= a[p]) break;          // parent smaller-or-equal: done
    [a[i], a[p]] = [a[p], a[i]];
    i = p;
  }
}
function insert(a, x) {
  a.push(x);                          // append at the end
  siftUp(a, a.length - 1);
}

def sift_up(a, i):
    while i > 0:
        p = (i - 1) // 2
        if a[i] >= a[p]:        # parent smaller-or-equal: done
            break
        a[i], a[p] = a[p], a[i]
        i = p

def insert(a, x):
    a.append(x)                 # append at the end
    sift_up(a, len(a) - 1)

Extract-min: swap root with last, then sift down

The minimum is always at the root (a[0]). To remove it: swap the root with the last element, pop the last element off (the old min), then sift down the new root — repeatedly swapping it with its smaller child until both children are larger or it becomes a leaf. Again O(log n).

int extractMin(std::vector<int>& a) {
    int top = a[0];
    a[0] = a.back();            // move last element to root
    a.pop_back();
    int i = 0, n = (int)a.size();
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, smallest = i;
        if (l < n && a[l] < a[smallest]) smallest = l;
        if (r < n && a[r] < a[smallest]) smallest = r;
        if (smallest == i) break;
        std::swap(a[i], a[smallest]);
        i = smallest;
    }
    return top;
}

int extractMin(List<Integer> a) {
    int top = a.get(0);
    int last = a.remove(a.size() - 1);
    if (!a.isEmpty()) {
        a.set(0, last);                 // move last element to root
        int i = 0, n = a.size();
        while (true) {
            int l = 2*i + 1, r = 2*i + 2, smallest = i;
            if (l < n && a.get(l) < a.get(smallest)) smallest = l;
            if (r < n && a.get(r) < a.get(smallest)) smallest = r;
            if (smallest == i) break;
            Collections.swap(a, i, smallest);
            i = smallest;
        }
    }
    return top;
}

function extractMin(a) {
  const top = a[0];
  const last = a.pop();
  if (a.length > 0) {
    a[0] = last;                        // move last element to root
    let i = 0;
    const n = a.length;
    while (true) {
      const l = 2*i + 1, r = 2*i + 2;
      let smallest = i;
      if (l < n && a[l] < a[smallest]) smallest = l;
      if (r < n && a[r] < a[smallest]) smallest = r;
      if (smallest === i) break;
      [a[i], a[smallest]] = [a[smallest], a[i]];
      i = smallest;
    }
  }
  return top;
}

def extract_min(a):
    top = a[0]
    last = a.pop()
    if a:
        a[0] = last                     # move last element to root
        i, n = 0, len(a)
        while True:
            l, r, smallest = 2*i + 1, 2*i + 2, i
            if l < n and a[l] < a[smallest]: smallest = l
            if r < n and a[r] < a[smallest]: smallest = r
            if smallest == i:
                break
            a[i], a[smallest] = a[smallest], a[i]
            i = smallest
    return top

Pitfall: When sifting down, always compare against the smaller (for a min-heap) of the two children — swapping with the larger child breaks the property. And remember to bound-check both child indices against the current size.

Build-heap: heapify an array in O(n)

Given an arbitrary array, you could insert each element one by one in O(n log n). But there’s a faster way: sift down every non-leaf node, starting from the last non-leaf (index n/2 - 1) and working backward to the root. Surprisingly this is O(n), not O(n log n), because most nodes are near the bottom and sift down only a step or two. (Full proof and heap sort are on the heapify & heap sort page.)

void siftDown(std::vector<int>& a, int i, int n) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, smallest = i;
        if (l < n && a[l] < a[smallest]) smallest = l;
        if (r < n && a[r] < a[smallest]) smallest = r;
        if (smallest == i) break;
        std::swap(a[i], a[smallest]);
        i = smallest;
    }
}
void buildHeap(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
}

void siftDown(int[] a, int i, int n) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, smallest = i;
        if (l < n && a[l] < a[smallest]) smallest = l;
        if (r < n && a[r] < a[smallest]) smallest = r;
        if (smallest == i) break;
        int t = a[i]; a[i] = a[smallest]; a[smallest] = t;
        i = smallest;
    }
}
void buildHeap(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
}

function siftDown(a, i, n) {
  while (true) {
    const l = 2*i + 1, r = 2*i + 2;
    let smallest = i;
    if (l < n && a[l] < a[smallest]) smallest = l;
    if (r < n && a[r] < a[smallest]) smallest = r;
    if (smallest === i) break;
    [a[i], a[smallest]] = [a[smallest], a[i]];
    i = smallest;
  }
}
function buildHeap(a) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
}

def sift_down(a, i, n):
    while True:
        l, r, smallest = 2*i + 1, 2*i + 2, i
        if l < n and a[l] < a[smallest]: smallest = l
        if r < n and a[r] < a[smallest]: smallest = r
        if smallest == i:
            break
        a[i], a[smallest] = a[smallest], a[i]
        i = smallest

def build_heap(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)

Complexity recap

Operation	Time	Why
peek (root)	O(1)	it’s `a[0]`
insert	O(log n)	sift up at most the tree height
extract	O(log n)	sift down at most the tree height
build-heap	O(n)	most nodes sift only a little

Going deeper: A max-heap is identical — just flip every < to > so the largest child wins. In production you rarely hand-roll this: you use a priority queue, which wraps exactly these operations.

Practice these on the heap exercises.