How to Build a Heap Tutorial | Learn Data Structures

What Is Build Heap?

Build Heap is the process of converting an unsorted array into a valid binary heap. The resulting structure can be either a Min Heap or a Max Heap, depending on the required ordering.

A binary heap must satisfy two conditions:

It must maintain the structure of a complete binary tree.
It must satisfy the appropriate heap-order property.

For a Min Heap, every parent must be less than or equal to its children. For a Max Heap, every parent must be greater than or equal to its children.

Example of Building a Heap

Consider the unsorted array:

[20, 5, 15, 2, 10, 8]

After building a Min Heap, one valid result is:

[2, 5, 8, 20, 10, 15]

This represents:

Every parent is less than or equal to its children, so the result satisfies the Min Heap property.

Two Ways to Build a Heap

There are two common approaches for converting a collection of values into a heap.

Insert each element one at a time into an initially empty heap.
Use bottom-up heap construction with heapify down.

Method	Approach	Time
Repeated insertion	Insert every value and heapify up	O(n log n)
Bottom-up construction	Heapify internal nodes from bottom to top	O(n)

Bottom-Up Heap Construction

The standard efficient approach to build a heap is called bottom-up heap construction.

Instead of inserting each element separately, the algorithm treats the input array as a complete binary tree and applies heapify down to every internal node, starting from the last internal node and moving toward the root.

Why Start from the Bottom?

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

The first node that can have children is the last internal node. With zero-based array indexing, its position is:

Math.floor(n / 2) - 1

From that index, the algorithm moves backward until it reaches index 0.

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

Build a Min Heap Step by Step

Consider the following array:

[20, 5, 15, 2, 10, 8]

Treating it as a complete binary tree gives:

There are six elements, so the last internal node is:

Math.floor(6 / 2) - 1
= 2

We therefore start heapifying at index 2.

Step 1: Heapify Index 2

The value at index 2 is 15, and its child is 8. Since this is a Min Heap, the smaller child should move upward.

Step 2: Heapify Index 1

The value at index 1 is 5. Its children are 2 and 10. Since 2 is smaller than 5, they are swapped.

The value 5 is now at a leaf position, so no further adjustment is required.

Step 3: Heapify the Root

The root is 20, with children 2 and 8. The smaller child is 2, so they are swapped.

The value 20 is now compared with its children 5 and 10. The smaller child is 5, so another swap occurs.

The resulting array is:

[2, 5, 8, 20, 10, 15]

Every parent is now less than or equal to its children, so the array is a valid Min Heap.

Build a Max Heap

Building a Max Heap follows exactly the same bottom-up process, but heapify down uses the larger child instead of the smaller child.

Consider:

[20, 5, 15, 2, 10, 8]

A valid Max Heap representation is:

[20, 10, 15, 2, 5, 8]

The root contains the largest value, and every parent is greater than or equal to its children.

Build Heap Algorithm

The general bottom-up build heap algorithm is:

Start with the unsorted array.
Treat the array as a complete binary tree.
Find the last internal node.
Apply heapify down to that node.
Move to the previous internal node.
Continue until the root is processed.
The resulting array is a valid heap.

Build Min Heap in JavaScript

The following implementation converts an unsorted array into a Min Heap using bottom-up construction.

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

  function heapifyDown(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;
    }
  }

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

  return heap;
}

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

const minHeap = buildMinHeap(values);

console.log(minHeap);
// [2, 5, 8, 20, 10, 15]

Build Max Heap in JavaScript

For a Max Heap, the heapify-down comparison is reversed.

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

  function heapifyDown(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;
    }
  }

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

  return heap;
}

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

const maxHeap = buildMaxHeap(values);

console.log(maxHeap);
// [20, 10, 15, 2, 5, 8]

Why Build Heap Is O(n)

A single heapify-down operation can take O(log n), but bottom-up heap construction does not perform O(log n) work for every element.

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

When the work performed by all internal nodes is combined, the total complexity is O(n).

Build Heap vs Repeated Insertion

Both methods can produce a valid heap, but they have different time complexities.

Repeated Insertion

Start with an empty heap and insert every value individually.

const heap = [];

for (const value of values) {
  insert(heap, value);
}

Each insertion can take O(log n), resulting in O(n log n) total time.

Bottom-Up Construction

Start with the complete array and heapify internal nodes from bottom to top.

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

This approach takes O(n) time.

Build Heap Complexity Comparison

Approach	Time	Extra Space
Repeated insertion	O(n log n)	Depends on implementation
Bottom-up build heap	O(n)	O(1) auxiliary when done in-place

In-Place Build Heap

Build heap can be performed directly on the input array without creating another array. This is called in-place heap construction.

function buildMinHeapInPlace(heap) {
  function heapifyDown(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;
    }
  }

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

  return heap;
}

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

buildMinHeapInPlace(values);

console.log(values);

The input array itself becomes the heap, so no second array is required.

Build Heap for a Min Heap vs Max Heap

Feature	Min Heap	Max Heap
Root	Smallest value	Largest value
Heapify down	Choose smaller child	Choose larger child
Parent rule	Parent ≤ children	Parent ≥ children
Build complexity	O(n)	O(n)

Build Heap and Heap Sort

Build heap is an important first step in Heap Sort. Heap Sort commonly builds a Max Heap and then repeatedly moves the largest value to its final position.

The heap construction phase takes O(n), while the repeated extraction or heap restoration phase takes O(n log n). Therefore, Heap Sort has an overall time complexity of O(n log n).

Build Heap and Priority Queues

Build heap is also useful when a collection of existing items needs to become a priority queue.

const tasks = [
  { name: "Report", priority: 3 },
  { name: "Critical Alert", priority: 10 },
  { name: "Email", priority: 5 }
];

A heap can be built from these items using their priority as the comparison key. After construction, the highest- or lowest-priority item can be accessed at the root, depending on the heap type.

Build Heap Does Not Sort the Array

A common misconception is that building a heap sorts the input. It does not.

For example, this is a valid Min Heap:

[2, 5, 8, 20, 10, 15]

But the array is not sorted because 20 appears before 10 and 15.

The important requirement is the parent-child relationship, not the ordering of all array elements.

Common Build Heap Mistakes

Starting from the Root

Bottom-up construction starts at the last internal node and moves toward the root. Starting from the root does not follow the standard bottom-up build process.

Heapifying Leaf Nodes

Leaf nodes have no children, so they already satisfy the heap property and do not need heapify down.

Choosing the Wrong Child

Min Heap construction must choose the smaller child during heapify down. Max Heap construction must choose the larger child.

Assuming Build Heap Is O(n log n)

Repeated insertion is O(n log n), but bottom-up heap construction is O(n).

Assuming the Result Is Sorted

Build heap creates a valid heap, not a sorted array.

When to Use Build Heap

Bottom-up build heap is useful when an entire collection of values is already available and needs to be converted into a heap efficiently.

Creating a priority queue from existing values.
Preparing data for Heap Sort.
Building a Min Heap for repeated minimum extraction.
Building a Max Heap for repeated maximum extraction.
Preparing heap-based algorithm input.
Initializing heap structures from bulk data.

Build Heap Complexity

Operation	Time Complexity	Space
Bottom-up Build Heap	O(n)	O(1) auxiliary in-place
Repeated insertion	O(n log n)	Depends on implementation
Single heapify down	O(log n)	O(1) iterative
Single heapify up	O(log n)	O(1) iterative

Key Takeaways

Build Heap converts an unsorted array into a valid heap.
Bottom-up construction starts from the last internal node.
Leaf nodes do not need heapify down.
Min Heap construction chooses the smaller child.
Max Heap construction chooses the larger child.
Bottom-up Build Heap takes O(n) time.
Building through repeated insertion takes O(n log n).
Build Heap does not sort the input array.
Heap construction can be performed in-place with O(1) auxiliary space.
Build Heap is an important component of Heap Sort and priority queue construction.

Topics

How to Build a Heap