Heap Data Structure: Introduction Tutorial

What Is a Heap Data Structure?

A Heap is a specialized tree-based data structure that maintains a specific ordering relationship between a parent node and its children. Heaps are commonly used when an application needs efficient access to the smallest or largest element.

A heap is usually implemented as a complete binary tree. Unlike a Binary Search Tree, a heap does not require every value in the left subtree to be smaller than every value in the right subtree.

The two fundamental types are:

Min Heap: The smallest value is stored at the root.
Max Heap: The largest value is stored at the root.

Heap Structure

A binary heap is a complete binary tree. This means every level is completely filled except possibly the last level, and nodes in the last level are filled from left to right.

The tree above is complete because each level is filled from left to right.

Heap Property

The defining characteristic of a heap is its heap property. The relationship between a parent and its children depends on whether the heap is a min heap or max heap.

Min Heap Property

In a min heap, every parent is less than or equal to its children.

The root contains the minimum value in the heap.

Max Heap Property

In a max heap, every parent is greater than or equal to its children.

The root contains the maximum value in the heap.

Min Heap vs Max Heap

Feature	Min Heap	Max Heap
Root	Smallest value	Largest value
Parent relationship	Parent ≤ children	Parent ≥ children
Common use	Minimum-priority item	Maximum-priority item

Why Is a Heap a Complete Binary Tree?

The complete-tree requirement allows a binary heap to be represented efficiently using an array. There is no need to store explicit left and right child references.

For an array-based heap using 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

const heap = [10, 20, 15, 40, 30];

console.log(heap[0]);
// 10

console.log(heap[1]);
// 20

console.log(heap[2]);
// 15

The array represents the tree:

Array Representation of a Heap

Consider the following max heap:

Its array representation is:

[90, 70, 80, 40, 60, 50]

Because the tree is complete, the elements can be stored continuously in the array.

Heap Insertion

When a new element is inserted into a heap, it is first placed at the next available position to preserve the complete-tree structure.

The new value may violate the heap property. The algorithm then moves it upward until the correct parent-child relationship is restored. This operation is called heapify up, sift up, or bubble up.

Example: Inserting into a Min Heap

Initial heap:

        10
       /  \
      20   15
     /
    40

Array:
[10, 20, 15, 40]

Insert 5 at the next available position:

The value 5 is smaller than its parent 20, so they are swapped. The value then continues upward because it is also smaller than 10.

Removing the Root

Removing the root is another important heap operation. Since the root contains the minimum value in a min heap or the maximum value in a max heap, removing it is commonly used to process the highest- or lowest-priority element.

A typical removal process is:

Save the root value.
Move the last element to the root.
Remove the last array element.
Restore the heap property by moving the new root downward.

This downward operation is called heapify down, sift down, or bubble down.

Peek Operation

The peek operation returns the root without removing it.

For a min heap:

const minHeap = [5, 10, 15, 40, 20];

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

For a max heap, the root contains the largest value.

const maxHeap = [90, 70, 80, 40, 60];

console.log(maxHeap[0]);
// 90

Heapify

Heapify is the process of restoring the heap property when the relationship between a node and its children has been disturbed.

Heapify is commonly used after removing the root and while constructing a heap from an existing array.

For a min heap, a node is compared with its children and swapped with the smaller child when necessary.

For a max heap, the node is swapped with the larger child when necessary.

Heap Operations and Complexity

Operation	Time Complexity
Peek	O(1)
Insert	O(log n)
Remove root	O(log n)
Search arbitrary value	O(n)
Build heap	O(n)

Heap insertion and root removal take O(log n) because the element can move through at most the height of the binary heap. Since a complete binary tree has logarithmic height, these operations remain efficient.

Why Heap Height Is O(log n)

A complete binary tree grows exponentially as levels are added. A heap containing n elements therefore has height proportional to log n.

Level 0 → 1 node
Level 1 → 2 nodes
Level 2 → 4 nodes
Level 3 → 8 nodes
...

This logarithmic height is what allows heapify operations to move an element through only a small number of levels.

Building a Min Heap in JavaScript

JavaScript does not provide a built-in general-purpose binary heap class, so a heap can be implemented using an array and helper methods.

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

Building a Max Heap in JavaScript

A max heap uses the same array representation, but the comparison is reversed so that larger values move toward the root.

class MaxHeap {
  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 MaxHeap();

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

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

console.log(heap.peek());
// 50

Heap vs Binary Search Tree

A heap and a Binary Search Tree are both tree-based data structures, but they maintain different ordering rules.

Feature	Heap	Binary Search Tree
Main ordering	Parent-child relationship	Left < root < right
Root	Minimum or maximum	Depends on inserted values
Shape	Complete binary tree	Not necessarily complete
Peek min/max	O(1)	Depends on tree balance
Typical representation	Array	Nodes and references

Heap vs Sorted Array

A sorted array provides direct access to its smallest or largest value, but maintaining sorted order during insertion can require shifting many elements.

A heap does not maintain complete sorted order. Instead, it maintains only the relationship necessary to efficiently access the highest- or lowest-priority element.

Heap and Priority Queues

A priority queue is an abstract data type in which elements are processed according to priority rather than simply according to insertion order. A heap is one of the most common data structures used to implement a priority queue.

For example, a min heap can process the task with the smallest priority value first.

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

// A priority queue could process:
// Security alert
// Email report
// Database backup

Common Applications of Heaps

Heaps are useful in systems and algorithms where repeatedly selecting the smallest or largest item is important.

Priority queues.
CPU and task scheduling.
Dijkstra's shortest path algorithm.
Prim's minimum spanning tree algorithm.
Heap Sort.
Finding the kth smallest or largest element.
Top-k problems.
Event scheduling.
Merging sorted collections.

Heap Sort and Heaps

Heap Sort uses a heap to repeatedly extract the largest or smallest element. A max heap is commonly used to produce ascending order through repeated extraction.

Heap Sort has a time complexity of O(n log n) and can be implemented with constant auxiliary space when performed in-place.

Common Heap Mistakes

Confusing a Heap with a Fully Sorted Tree

A heap does not keep all elements globally sorted. Only the parent-child heap property is guaranteed.

Assuming Arbitrary Search Is O(log n)

A heap efficiently exposes the root, but it does not provide the same ordering as a Binary Search Tree. Searching for an arbitrary value can require examining many nodes and has O(n) worst-case complexity.

Using the Wrong Child During Heapify

During heapify down, the node must be compared against the appropriate child. A min heap selects the smaller child, while a max heap selects the larger child.

Forgetting the Complete-Tree Requirement

A binary heap is not simply any binary tree with a parent-child ordering. Its complete shape is what enables the efficient array representation.

Heap Operations Summary

Operation	Purpose	Complexity
Peek	Read root without removing it	O(1)
Insert	Add and restore heap property	O(log n)
Extract root	Remove minimum or maximum	O(log n)
Heapify	Restore local heap property	O(log n)
Build heap	Create heap from an array	O(n)

Key Takeaways

A heap is a complete binary tree with a parent-child ordering property.
A min heap keeps the smallest element at the root.
A max heap keeps the largest element at the root.
Binary heaps are commonly represented using arrays.
Insertion uses heapify up and takes O(log n).
Removing the root uses heapify down and takes O(log n).
Peeking at the root takes O(1).
Building a heap from an array can be done in O(n).
Heaps are commonly used to implement priority queues.
A heap is not the same as a Binary Search Tree or a sorted array.

Topics

Heap Data Structure: Introduction