Heapify: Build and Maintain a Heap Tutorial

What Is Heapify?

Heapify is the process of rearranging elements so that they satisfy the ordering property of a heap. It is one of the most important operations used when creating and maintaining Min Heaps and Max Heaps.

Heapify does not mean sorting the entire collection. Instead, it restores the local parent-child relationships required by the heap.

There are two common forms of heapify:

Heapify Up: moves an element toward the root.
Heapify Down: moves an element toward the leaves.

Heapify and the Heap Property

A binary heap must satisfy two conditions: it must have the structure of a complete binary tree, and it must satisfy the correct parent-child ordering.

For a Min Heap:

Parent ≤ Child

For a Max Heap:

Parent ≥ Child

Heapify is the mechanism used to restore these relationships when an operation temporarily violates them.

Heapify Up

Heapify up is used when a newly inserted or updated element may violate the heap property with its parent.

The element is compared with its parent. If the ordering is incorrect, the two values are swapped. The process continues until the element reaches a valid position or becomes the root.

Heapify Up in a Min Heap

In a Min Heap, a child must not be smaller than its parent.

Before insertion:

        10
       /  \
      20   15

Insert 5:

        10
       /  \
      20   15
     /
    5

The new value 5 is smaller than its parent 20, so they are swapped.

The value 5 is still smaller than its new parent 10, so another swap is required.

The Min Heap property is now restored.

Heapify Up in a Max Heap

In a Max Heap, the child must not be greater than its parent.

Since 70 is greater than its parent 30, they are swapped. The value then continues upward until the Max Heap property is restored.

Heapify Up Algorithm

Start at the newly inserted element.
Calculate its parent index.
Compare the element with its parent.
Swap them if the heap property is violated.
Move to the parent's position.
Repeat until the property is restored or the root is reached.

Because the heap height is O(log n), heapify up takes at most O(log n) time.

Heapify Down

Heapify down moves an element toward the leaves when its value may violate the heap property with its children.

Heapify down is commonly used after removing the root of a heap. The last element is moved to the root, and that element is then moved downward until the heap property is restored.

Heapify Down in a Min Heap

Before extraction:

        5
       / \
      10  8
     / \
    20 15

Remove 5 and move 15 to root:

        15
       /  \
      10    8
     /
    20

The new root 15 is greater than both children. The smaller child is 8, so 15 is swapped with 8.

The Min Heap property has been restored.

Heapify Down in a Max Heap

In a Max Heap, the larger child is selected when both children need to be considered.

Before:

        90
       /  \
      70   80
     / \
    40 60

Remove 90 and move 60:

        60
       /  \
      70   80

The larger child is 80, so the correct swap is:

        80
       /  \
      70   60

The Max Heap property is restored.

Why Does Heapify Down Choose One Child?

Choosing the correct child is essential because the resulting parent must satisfy the heap property with both children.

For a Min Heap, choose the smaller child:

If 30 were swapped with 20 instead, the resulting tree would still violate the Min Heap property because 20 > 10 would leave the parent larger than its other child.

For a Max Heap, choose the larger child:

Heapify Using Array Indexes

Binary heaps are commonly represented using arrays. With zero-based indexing, the parent and child positions are calculated as follows:

Relationship	Formula
Parent of i	Math.floor((i - 1) / 2)
Left child	2 * i + 1
Right child	2 * i + 2

const heap = [5, 10, 8, 20, 15, 12];

// Tree:
//
//        5
//       / \
//      10  8
//     / \  /
//    20 15 12

Iterative Heapify Down for a Min Heap

The iterative approach repeatedly compares the current element with its children and swaps it with the smaller child when necessary.

function minHeapifyDown(heap, index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;

    let smallest = index;

    if (
      left < heap.length &&
      heap[left] < heap[smallest]
    ) {
      smallest = left;
    }

    if (
      right < heap.length &&
      heap[right] < heap[smallest]
    ) {
      smallest = right;
    }

    if (smallest === index) {
      break;
    }

    [heap[index], heap[smallest]] =
      [heap[smallest], heap[index]];

    index = smallest;
  }
}

const heap = [30, 10, 20, 40, 50, 5];

minHeapifyDown(heap, 0);

console.log(heap);

Iterative Heapify Down for a Max Heap

A Max Heap uses the same process, but selects the larger child.

function maxHeapifyDown(heap, index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;

    let largest = index;

    if (
      left < heap.length &&
      heap[left] > heap[largest]
    ) {
      largest = left;
    }

    if (
      right < heap.length &&
      heap[right] > heap[largest]
    ) {
      largest = right;
    }

    if (largest === index) {
      break;
    }

    [heap[index], heap[largest]] =
      [heap[largest], heap[index]];

    index = largest;
  }
}

const heap = [30, 50, 40, 10, 20, 35];

maxHeapifyDown(heap, 0);

console.log(heap);

Recursive Heapify Down

Heapify down can also be implemented recursively. The current node is compared with its children, the appropriate child is selected, and the function continues from the swapped position.

function minHeapifyDown(heap, index) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  let smallest = index;

  if (
    left < heap.length &&
    heap[left] < heap[smallest]
  ) {
    smallest = left;
  }

  if (
    right < heap.length &&
    heap[right] < heap[smallest]
  ) {
    smallest = right;
  }

  if (smallest === index) {
    return;
  }

  [heap[index], heap[smallest]] =
    [heap[smallest], heap[index]];

  minHeapifyDown(heap, smallest);
}

The recursive version uses O(log n) call-stack space in the worst case, while an iterative implementation can perform the same operation using O(1) auxiliary space.

Heapify Up Implementation

Heapify up starts from a node and repeatedly compares it with its parent.

function minHeapifyUp(heap, index) {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);

    if (heap[parent] <= heap[index]) {
      break;
    }

    [heap[parent], heap[index]] =
      [heap[index], heap[parent]];

    index = parent;
  }
}

const heap = [10, 20, 15];

heap.push(5);

minHeapifyUp(heap, heap.length - 1);

console.log(heap);
// [5, 10, 15, 20]

Heapify During Insertion

Insertion first places the new value at the end of the array. This preserves the complete binary tree structure.

heap.push(value);
minHeapifyUp(heap, heap.length - 1);

This combination of insertion followed by heapify up gives a heap insertion operation with O(log n) time complexity.

Heapify During Root Extraction

When the root is extracted, the last element replaces it. The replacement may violate the heap property with its children.

const root = heap[0];

heap[0] = heap.pop();

minHeapifyDown(heap, 0);

The resulting extraction operation takes O(log n) time.

Build Heap Using Heapify

One of the most important applications of heapify is converting an unsorted array into a valid heap.

The bottom-up approach starts at the last internal node and applies heapify down toward the root.

function buildMinHeap(values) {
  const heap = [...values];

  for (
    let index = Math.floor(heap.length / 2) - 1;
    index >= 0;
    index--
  ) {
    minHeapifyDown(heap, index);
  }

  return heap;
}

const values = [20, 5, 15, 2, 10, 8];

console.log(buildMinHeap(values));

Why Start from the Last Internal Node?

Leaf nodes already satisfy the heap property because they do not have children. Therefore, there is no reason to heapify them.

With zero-based indexing, the last internal node is:

Math.floor(n / 2) - 1

The algorithm then moves backward toward index 0.

for (
  let index = Math.floor(heap.length / 2) - 1;
  index >= 0;
  index--
) {
  heapifyDown(heap, index);
}

Heapify vs Sorting

Heapify should not be confused with sorting.

Heapify	Sorting
Restores heap ordering	Orders the entire collection
Maintains parent-child relationships	Establishes a global ordering
Often O(log n) for one node	Usually requires more work for the entire collection
Used to maintain heaps	Used to arrange values

Heapify Complexity

Heapify Operation	Time	Auxiliary Space
Heapify up	O(log n)	O(1) iterative
Heapify down	O(log n)	O(1) iterative
Build heap	O(n)	O(1) auxiliary in-place

Why Bottom-Up Heapify Is O(n)

A single heapify-down operation can take O(log n), but building a heap does not perform O(log n) work for every node.

Most nodes are near the bottom of the tree and can move only a small number of levels. Only a few nodes near the root can move through many levels.

The combined work of all bottom-up heapify operations is therefore O(n).

Heapify Up vs Heapify Down

Feature	Heapify Up	Heapify Down
Direction	Toward root	Toward leaves
Common operation	Insertion	Root extraction
Min Heap	Swap when child < parent	Choose smaller child
Max Heap	Swap when child > parent	Choose larger child
Time	O(log n)	O(log n)

Common Heapify Mistakes

Choosing the Wrong Child

During Min Heap heapify down, choose the smaller child. During Max Heap heapify down, choose the larger child.

Checking Only One Child

When both children exist, both must be considered before deciding which child should replace the current node.

Using Heapify Up After Root Removal

After root extraction, the replacement value normally needs to move downward, so heapify down is the appropriate operation.

Heapifying Leaf Nodes

Leaf nodes have no children, so they do not require heapify down during bottom-up heap construction.

Confusing Heapify with Sorting

Heapify restores heap structure; it does not produce a completely sorted array.

Where Heapify Is Used

Heapify is a fundamental operation in several important data structure and algorithm techniques.

Building Min Heaps and Max Heaps
Priority queue implementations
Heap Sort
Dijkstra's algorithm with a priority queue
Top-k problems
Finding minimum or maximum values repeatedly
Scheduling and event processing
Maintaining dynamically changing priority data

Heapify Operation Summary

Concept	Main Idea	Complexity
Heapify up	Move a value toward the root	O(log n)
Heapify down	Move a value toward the leaves	O(log n)
Build heap	Heapify internal nodes bottom-up	O(n)
Min Heap down	Select the smaller child	O(log n)
Max Heap down	Select the larger child	O(log n)

Key Takeaways

Heapify restores the ordering property of a heap.
Heapify up moves an element toward the root.
Heapify down moves an element toward the leaves.
Heapify up is commonly used after insertion.
Heapify down is commonly used after root extraction.
Min Heap heapify down selects the smaller child.
Max Heap heapify down selects the larger child.
A single heapify-up or heapify-down operation takes O(log n).
Bottom-up heap construction takes O(n) time.
Heapify maintains heap order; it does not fully sort the data.

Topics

Heapify: Build and Maintain a Heap