Min Heap Data Structure

Learn Min Heap Data Structure with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Min Heap?

A Min Heap is a complete binary tree in which every parent node is less than or equal to its children. Because of this property, the smallest element is always stored at the root of the heap.

A Min Heap is useful when an application repeatedly needs access to the smallest value. It is commonly used to implement priority queues, scheduling systems, graph algorithms, and algorithms that repeatedly select the minimum element. 

        5
       / \
      10  8
     / \  /
    20 15 12

Every parent is smaller than or equal to its children, and the root contains the minimum value: 5.

Min Heap Property

The defining rule of a Min Heap is:

Parent value ≤ Child value

This rule must hold for every parent-child relationship in the heap. 

Valid Min Heap:

        10
       /  \
      20   15
     / \   /
    40 30 25

Notice that the heap does not need to be completely sorted. For example, 20 can be greater than 15 even though both are children of the root.

Min Heap Is a Complete Binary Tree

A Min Heap must also satisfy the structural property of a complete binary tree.

This means:

  • Every level is completely filled except possibly the last.
  • The final level is filled from left to right.
  • There are no gaps between nodes on the final level.
Complete:

        5
       / \
      8   10
     / \
    15 20

The complete-tree property allows a Min Heap to be stored efficiently inside an array.

Min Heap Array Representation

A binary Min Heap is usually represented using an array instead of separate tree nodes. Consider this heap: 

        5
       / \
      10  8
     / \  /
    20 15 12

Its array representation is: 

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

For zero-based indexing, the relationships are:

  • Parent of index i: Math.floor((i - 1) / 2)
  • Left child of index i: 2 * i + 1
  • Right child of index i: 2 * i + 2

Finding the Parent and Children

Suppose an element is stored at index 3. 

Parent:
Math.floor((3 - 1) / 2)
= 1

Left child:
2 * 3 + 1
= 7

Right child:
2 * 3 + 2
= 8

These formulas allow heap operations to move through the tree without explicit node objects or pointers.

Peek: Accessing the Minimum Value

Because the smallest value is always at the root, a Min Heap can return the minimum element without removing it in O(1) time. 

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

console.log(minHeap[0]);
// 5

This operation is commonly called peek.

Inserting an Element into a Min Heap

Insertion must preserve both the complete-tree structure and the Min Heap property. The new value is first placed at the end of the array, which corresponds to the next available position in the tree.

The new element is then moved upward while it is smaller than its parent. This process is called heapify up or sift up.

Example

Start with: 

        10
       /  \
      20   15
     / \
    40 30

Array: 

[10, 20, 15, 40, 30]

Insert 5. It is initially placed at the end: 

        10
       /  \
      20   15
     / \   /
    40 30  5

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

        10
       /  \
      20    5
     / \   /
    40 30 15

The value 5 is still smaller than its new parent 10, so another swap is performed: 

         5
       /   \
      20    10
     / \   /
    40 30 15

The Min Heap property has now been restored.

Min Heap Insertion Algorithm

  1. Add the new value to the end of the array.
  2. Find its parent index.
  3. Compare the value with its parent.
  4. If the value is smaller, swap them.
  5. Continue moving upward until the heap property is restored.

Removing the Minimum Element

The minimum element is always the root, so removing the minimum means removing the first element of the heap.

The typical process is:

  1. Save the root value.
  2. Move the last element to the root.
  3. Remove the final array element.
  4. Compare the new root with its children.
  5. Swap it with the smaller child when necessary.
  6. Continue until the Min Heap property is restored.

The downward restoration process is called heapify down or sift down.

Example of Extracting the Minimum

Consider: 

        5
       / \
      10   8
     / \  /
    20 15 12

Remove 5. Move the last element, 12, to the root: 

        12
       /  \
      10    8
     / \
    20 15

The value 12 is larger than both children. The smaller child is 8, so they are swapped: 

         8
       /   \
      10    12
     / \
    20 15

The Min Heap property has been restored.

Why Does Heapify Down Choose the Smaller Child?

Suppose the current node is larger than both children. In a Min Heap, it must move above the smaller child first. Choosing the larger child could leave a smaller child below the larger parent and violate the heap property. 

        20
       /  \
      8    12

The correct swap is with 8, not 12.

Building a Min Heap from an Array

An existing array can be transformed into a Min Heap. One efficient approach starts from the last non-leaf node and performs heapify down toward the root.

This process is called build heap. 

const values = [20, 10, 30, 5, 15, 40];

console.log(values);

// After building a Min Heap,
// one valid representation is:

[5, 10, 30, 20, 15, 40]

The resulting array does not have to be sorted. It only needs to satisfy the Min Heap property.

Min Heap Implementation in JavaScript

The following implementation provides insertion, minimum lookup, and extraction. 

class MinHeap {
  constructor() {
    this.heap = [];
  }

  peek() {
    return this.heap[0] ?? null;
  }

  insert(value) {
    this.heap.push(value);

    let index = this.heap.length - 1;

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

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

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

      index = parent;
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const minimum = this.heap[0];

    this.heap[0] = this.heap.pop();

    let index = 0;

    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let smallest = index;

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

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

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

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

      index = smallest;
    }

    return minimum;
  }
}

const minHeap = new MinHeap();

minHeap.insert(30);
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(5);
minHeap.insert(15);

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

console.log(minHeap.peek());
// 5

console.log(minHeap.extractMin());
// 5

console.log(minHeap.peek());
// 10

Min Heap Time Complexity

Operation Complexity Reason
Peek minimum O(1) Minimum is always at the root
Insert O(log n) Element may move up the heap
Extract minimum O(log n) Root may move down the heap
Search arbitrary value O(n) Heap is not globally sorted
Build heap O(n) Bottom-up heap construction

Min Heap Space Complexity

A Min Heap containing n elements requires O(n) storage. When represented using an array, the elements are stored directly in that array without separate left and right child objects.

Min Heap vs Max Heap

Feature Min Heap Max Heap
Root Smallest element Largest element
Parent rule Parent ≤ children Parent ≥ children
Extract operation Extract minimum Extract maximum
Typical use Minimum-priority processing Maximum-priority processing

Min Heap vs Sorted Array

Both a Min Heap and a sorted array can provide quick access to the smallest element, but they maintain different structures.

A sorted array keeps every element in order. A Min Heap only guarantees that each parent is smaller than or equal to its children. This weaker ordering allows the heap to support insertion and minimum extraction efficiently.

Operation Min Heap Sorted Array
Get minimum O(1) O(1)
Insert O(log n) O(n) typically
Remove minimum O(log n) Depends on representation
Arbitrary search O(n) O(log n) with binary search

Min Heap and Priority Queue

A Min Heap is one of the most common implementations of a priority queue. The element with the smallest priority value can remain at the root and be extracted efficiently. 

const tasks = [
  { name: "Database backup", priority: 3 },
  { name: "Security alert", priority: 1 },
  { name: "Send report", priority: 2 }
];

// A Min Heap ordered by priority would process:
//
// Security alert      → priority 1
// Send report        → priority 2
// Database backup    → priority 3

The heap does not need to sort every task globally. It only needs to keep the highest-priority task at the root.

Applications of Min Heap

Min Heaps are useful whenever the smallest available value must be selected repeatedly. Common applications include:

  • Priority queues.
  • Task scheduling.
  • Dijkstra's shortest path algorithm.
  • Prim's minimum spanning tree algorithm.
  • Finding the kth smallest element.
  • Merging multiple sorted lists.
  • Event scheduling.
  • Top-k and streaming problems.
  • Resource allocation systems.

Min Heap in Dijkstra's Algorithm

Dijkstra's algorithm repeatedly selects the unprocessed vertex with the smallest known distance. A Min Heap can efficiently provide the next smallest distance. 

Priority queue:

(distance, vertex)

(2, B)
(5, D)
(8, C)
(12, E)

The pair with distance 2 is extracted first.

This allows the algorithm to avoid scanning every unprocessed vertex to find the smallest distance.

Finding the Kth Smallest Element

A Min Heap can be used when a problem requires repeatedly extracting the smallest values. For example, extracting the minimum element k times can identify the kth smallest value. 

const values = [8, 3, 10, 2, 7, 5];

// After building a Min Heap,
// repeatedly extract the minimum.
//
// 1st smallest → 2
// 2nd smallest → 3
// 3rd smallest → 5
// 4th smallest → 7

Common Min Heap Mistakes

Thinking the Heap Is Fully Sorted

A Min Heap only guarantees that parents are smaller than or equal to their children. It does not guarantee that siblings or unrelated nodes are sorted.

Searching for Any Value in O(log n)

A Min Heap is optimized for finding the minimum, not arbitrary values. Searching for a specific element can take O(n) time.

Choosing the Wrong Child During Heapify Down

In a Min Heap, the current node should move toward the smaller child when both children exist and are smaller than the current node.

Forgetting the Complete-Tree Structure

The heap property alone is not enough. A binary heap must also maintain the complete binary tree structure so that its array representation remains valid.

Min Heap Operation Summary

Operation Description Time
Peek Read the minimum element O(1)
Insert Add an element and heapify up O(log n)
Extract Min Remove the root and heapify down O(log n)
Search Find an arbitrary value O(n)
Build Heap Create a heap from an array O(n)

Key Takeaways

  • A Min Heap is a complete binary tree.
  • Every parent is less than or equal to its children.
  • The smallest element is always at the root.
  • Min Heaps are commonly represented using arrays.
  • Peek returns the minimum in O(1) time.
  • Insertion uses heapify up and takes O(log n).
  • Extracting the minimum uses heapify down and takes O(log n).
  • Searching for an arbitrary value can take O(n).
  • Building a heap from an array can be performed in O(n).
  • Min Heaps are widely used for priority queues and shortest-path algorithms.

Code Examples 

class MinHeap {
  constructor() {
    this.heap = [];
  }

  peek() {
    return this.heap[0] ?? null;
  }

  insert(value) {
    this.heap.push(value);

    let index = this.heap.length - 1;

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

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

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

      index = parent;
    }
  }
}

const heap = new MinHeap();

heap.insert(30);
heap.insert(10);
heap.insert(20);
heap.insert(5);

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

console.log(heap.peek());
// 5
    
class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);

    let index = this.heap.length - 1;

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

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

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

      index = parent;
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const minimum = this.heap[0];

    this.heap[0] = this.heap.pop();

    let index = 0;

    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let smallest = index;

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

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

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

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

      index = smallest;
    }

    return minimum;
  }
}

const heap = new MinHeap();

[30, 10, 20, 5, 15].forEach(value => {
  heap.insert(value);
});

console.log(heap.extractMin());
// 5

console.log(heap.heap);
    
function kthSmallest(values, k) {
  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);
  }

  let result = null;

  for (let count = 0; count < k; count++) {
    result = heap[0];

    heap[0] = heap.pop();

    if (heap.length > 0) {
      heapifyDown(0);
    }
  }

  return result;
}

console.log(
  kthSmallest([8, 3, 10, 2, 7, 5], 3)
);
// 5

Pro Tip

Use a Min Heap when the smallest item needs to be available quickly while elements are continuously inserted or removed. The key pattern to remember is O(1) peek, O(log n) insert, and O(log n) extract-min.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.