Max Heapify and Build a Max Heap in Python and TypeScript

The Problem

A max heap is a complete binary tree where every parent is at least as large as its children, so the largest value is always at the root. It is stored in a plain array: the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i − 1) / 2 rounded down.

The interview task usually comes in three parts: write max heapify (sift a value down), use it to build a max heap from an unsorted array in place, and sometimes finish with heap sort.

Example 1

Input: [3, 9, 2, 1, 4, 5]. After building a max heap: [9, 4, 5, 1, 3, 2]. 9 is the root, and each parent is larger than its children: 9 over 4 and 5, 4 over 1 and 3, 5 over 2.

Example 2

Heap sort on the same input gives [1, 2, 3, 4, 5, 9]. Each step swaps the root (the current maximum) to the end of the array and sifts the new root down within the shrinking heap.

Assumptions to confirm

• Max heap or min heap? The logic is identical with the comparison flipped.
• In place, or may you allocate a new array?
• May you use the language's heap library, or should you write the operations yourself? For this question, usually yourself.

The Naive Approach

The obvious way to build a heap is to insert values one at a time, sifting each new value up from the bottom. Each insert costs up to O(log n), so building takes O(n log n). It is correct and worth mentioning, but the bottom-up method below is faster, and explaining why is the part interviewers listen for.

The Optimal Approach: Bottom-Up Heapify

Python and TypeScript Solutions

Python

def sift_down(a: list[int], i: int, size: int) -> None:
    """Move a[i] down until both children are smaller (max heap)."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


def build_max_heap(a: list[int]) -> None:
    """Heapify in place in O(n): sift down every parent, last parent first."""
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))


def heap_sort(a: list[int]) -> None:
    build_max_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]   # move the max to its final place
        sift_down(a, 0, end)

TypeScript

// Move a[i] down until both children are smaller (max heap).
function siftDown(a: number[], i: number, size: number): void {
  while (true) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest === i) return;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}

// Heapify in place in O(n): sift down every parent, last parent first.
function buildMaxHeap(a: number[]): void {
  for (let i = Math.floor(a.length / 2) - 1; i >= 0; i--) siftDown(a, i, a.length);
}

function heapSort(a: number[]): void {
  buildMaxHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]]; // move the max to its final place
    siftDown(a, 0, end);
  }
}

Python's heapq is a min-heap

In day-to-day code you would use the standard library. Python's heapq only provides a min-heap, so the usual trick for a max heap is to store negated numbers. heapq.heapify also runs in O(n).

import heapq

nums = [3, 9, 2, 1, 4, 5]
heap = [-n for n in nums]   # heapq is a min-heap, so store negatives
heapq.heapify(heap)         # O(n)
largest = -heap[0]          # 9

JavaScript and TypeScript have no built-in heap, which is why interviewers often ask TypeScript candidates to write one.

Complexity Compared

Why Building a Heap Is O(n), Not O(n log n)

This is the follow-up question most candidates struggle with. Sift-down costs time proportional to a node's height, not the tree's full height. Half the nodes are leaves and cost nothing, a quarter sit one level up and move at most one step, an eighth move at most two steps, and so on. Adding that up gives a total that stays below a small constant times n, so bottom-up heapify is linear. Inserting values one at a time is slower because every insert can travel the full height of the tree.

How to Talk Through It in an Interview

1. Clarify: "Max heap, in place, and I write the operations myself rather than using a library?"
2. Explain the layout: "The heap lives in an array: children of i are 2i + 1 and 2i + 2."
3. Naive: "Inserting one value at a time works, at O(n log n)."
4. Optimise: "Bottom-up heapify sifts down each parent from the last one, which is O(n) because most nodes are near the bottom."
5. Test: an empty array, one element, all-equal values, an already sorted array and a reverse sorted one.

Edge Cases and Follow-Ups

Practise It in a Mock Coding Round

Reading a solution is not the same as producing it with someone watching. In a real round you have to clarify the problem, say the brute force out loud, and keep talking while you type. MockIF runs coding rounds with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, follows up on edge cases and complexity, then scores the round and gives you specific feedback. A session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing). Read more about how a mock coding interview works.

Frequently Asked Questions