Overview

A heap is a tree-based structure optimized for repeatedly processing the minimum or maximum value. Heaps power priority queues, scheduling systems, Heap Sort, and graph algorithms. They are complete binary trees but maintain only a parent-child ordering rather than a fully sorted order.

Key concepts

• A heap is a complete binary tree
• A Min Heap keeps the smallest value at the root
• A Max Heap keeps the largest value at the root
• Heaps are normally stored compactly in arrays

What is a Heap?

A complete binary tree fills every level except possibly the last, and fills the last level from left to right without gaps.

        10
       /       20    30
    /     /
   40 50  60

This shape is complete because each position is filled from left to right.

Types of Heaps

Min Heap

Every parent is less than or equal to its children, so the smallest value is always at the root.

        10
       /       20    30
    /     /
   40 50  60

Max Heap

Every parent is greater than or equal to its children, so the largest value is always at the root.

        60
       /       50    40
    /     /
   20 10  30

A heap does not guarantee that all values are globally sorted. It guarantees only the required relationship between each parent and its children.

How is a Heap stored?

The complete shape lets a heap use an array without separate child references. Nodes appear in level order.

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

Inserting an Element

Add the value at the end to preserve the complete shape. Then compare it with its parent and swap while it violates the heap property. This restoration process is called heapify up or bubble up.

If 5 is inserted into a Min Heap rooted at 10, it first occupies the next open position, swaps with 20, and then swaps with 10 to become the new root.

const heap = [10, 20, 30, 40];
heap.push(5);

let index = heap.length - 1;

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

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

  [heap[parentIndex], heap[index]] =
    [heap[index], heap[parentIndex]];

  index = parentIndex;
}

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

The resulting array is not fully sorted, but it satisfies the Min Heap property.

Removing the Root

Removing the root extracts the minimum from a Min Heap or maximum from a Max Heap.

• Save the root value
• Move the last value to the root
• Remove the final array position
• Compare the new root with its children
• Swap downward until the heap property is restored

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

Time complexity of Heap operations

The root is always at array index 0. Insertion and removal follow at most one root-to-leaf path, while searching for an arbitrary value may require checking the entire heap.

Heap vs Binary Search Tree

Where are Heaps used?

• Priority queues
• CPU task scheduling
• Emergency-room triage
• Heap Sort
• Top-k and smallest-or-largest problems
• Dijkstra's shortest-path algorithm
• Prim's minimum spanning tree algorithm
• Priority-based job processing

For example, a hospital priority queue can process critical patients before less urgent cases even if they arrived later.

Key takeaways

• A heap is a complete binary tree
• Min Heaps expose the smallest value
• Max Heaps expose the largest value
• Array indexes encode parent-child relationships
• Peek is O(1)
• Insertion and root removal are O(log n)
• A heap is partially ordered rather than fully sorted
• Heaps are ideal for priority-driven processing