Heap Operations: Insert, Delete and Peek Tutorial

What Are Heap Operations?

Heap operations are the procedures used to maintain and work with a heap data structure. A binary heap is a complete binary tree that follows either the Min Heap or Max Heap property.

The most common heap operations are:

Peek at the root element
Insert a new element
Extract the minimum or maximum element
Heapify up
Heapify down
Build a heap from an existing array
Replace the root element
Convert an array into a Min Heap or Max Heap

These operations are designed to preserve both the complete binary tree structure and the appropriate heap-order property.

Heap Operations at a Glance

Operation	Typical Time	Purpose
Peek	O(1)	Read the root element
Insert	O(log n)	Add an element while preserving heap order
Extract root	O(log n)	Remove the minimum or maximum element
Heapify up	O(log n)	Move an element toward the root
Heapify down	O(log n)	Move an element toward the leaves
Build heap	O(n)	Create a heap from an unsorted array
Search arbitrary value	O(n)	Find a value that is not necessarily the root

1. Peek Operation

The peek operation reads the root element without removing it.

Because the root always contains the extreme value:

A Min Heap stores the smallest value at the root.
A Max Heap stores the largest value at the root.

Min Heap:

        5
       / \
      10  8

Peek → 5


Max Heap:

        50
       /  \
      30   40

Peek → 50

When a heap is represented using an array, the root is stored at index 0.

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

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

The peek operation takes O(1) time.

2. Inserting an Element

Insertion adds a new value while preserving the complete binary tree structure and restoring the heap-order property if necessary.

Insertion Process

Add the new element at the end of the array.
Compare it with its parent.
Swap it with the parent if the heap property is violated.
Continue moving upward until the heap property is restored.

The upward adjustment is called heapify up, also known as sift up or bubble up.

Min Heap Insertion Example

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

Now 5 is smaller than 10, so another swap is performed.

The Min Heap property has been restored.

3. Heapify Up

Heapify up is used when an element may be smaller than its parent in a Min Heap or larger than its parent in a Max Heap.

The operation repeatedly compares the current node with its parent and swaps them when necessary.

Min Heap:

Current node < Parent
        ↓
    swap with parent
        ↓
check again
        ↓
stop when property is restored

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

4. Extracting the Root

Extraction removes the root element from the heap.

In a Min Heap, this is called extract-min.
In a Max Heap, this is called extract-max.

The root cannot simply be removed because that would leave a hole at the top of the complete tree. Instead, the last element is moved to the root.

Extraction Process

Save the root value.
Move the last element to index 0.
Remove the final array element.
Compare the new root with its children.
Swap it with the appropriate child when required.
Continue downward until the heap property is restored.

This downward adjustment is called heapify down or sift down.

Min Heap Extraction Example

Before:

        5
       / \
      10  8
     / \
    20 15

Extract 5.

Move 15 to the root:

        15
       /  \
      10    8
     /
    20

The value 15 is greater than both children. The smaller child is 8, so they are swapped.

The heap property is restored.

5. Heapify Down

Heapify down is normally required after removing the root or moving a value into a position where it may violate the heap-order property with its children.

The child selection depends on the heap type:

Min Heap: choose the smaller child.
Max Heap: choose the larger child.

Min Heap:

        30
       /  \
      10   20

Swap with 10 because it is the smaller child.


Max Heap:

        30
       /  \
      50   40

Swap with 50 because it is the larger child.

Heapify down takes O(log n) time because an element can move through at most the height of the heap.

6. Build Heap from an Array

A heap can be created from an existing unsorted array using bottom-up heap construction.

Instead of inserting every value one by one, the algorithm starts from the last non-leaf node and performs heapify down toward the root.

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

Build a Min Heap:

        2
       / \
      5    8
     / \  /
    20 10 15

Bottom-up heap construction takes O(n) time.

Why Build Heap Is O(n)

It may seem that heapifying every node should take O(n log n), but most nodes are close to the bottom of the tree and can move only a short distance.

Only a small number of nodes are high enough to require long downward movements. The total work of bottom-up heap construction is therefore O(n).

7. Build Heap by Repeated Insertion

Another way to create a heap is to start with an empty heap and insert each element individually.

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

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

Each insertion can take O(log n), so building a heap through repeated insertion takes O(n log n) in the worst case.

When the entire input is already available, bottom-up heap construction is generally the more direct way to build a heap.

8. Insert vs Build Heap

Approach	How It Works	Time
Repeated insertion	Insert every element individually	O(n log n)
Bottom-up build heap	Heapify internal nodes from bottom to top	O(n)

9. Updating an Element

Updating a value inside a heap may require restoring the heap property. The direction of adjustment depends on how the value changed.

In a Min Heap:

If a value becomes smaller, it may need to move upward.
If a value becomes larger, it may need to move downward.

In a Max Heap, the directions are reversed.

Min Heap:

        5
       / \
      10  8

Change 10 → 2

         5
       / \
      2    8

The value 2 must move upward.

The update operation itself may be O(1), but restoring the heap property can take O(log n).

10. Replacing the Root

A heap can also replace its root with a new value and then restore the heap property. This can be useful when processing priority-based data.

For example, in a Min Heap, replacing the root with a larger value usually requires heapify down.

Before:

        5
       / \
      10  8

Replace root with 20:

        20
       /  \
      10   8

Heapify down:

         8
       / \
      10  20

11. Removing an Arbitrary Element

Standard heap operations are optimized around the root. Removing an arbitrary element requires first finding its position.

Since a heap is not fully sorted, finding an arbitrary value can require O(n) time.

After locating the value, it can be replaced with the last element and the heap property can be restored by moving the replacement upward or downward as necessary.

12. Searching in a Heap

A heap provides fast access to the root, but it is not designed for arbitrary search.

Knowing that 5 is the minimum does not tell us exactly where another arbitrary value is located.

Therefore, searching for an arbitrary value generally takes O(n) time.

JavaScript Min Heap Implementation

The following implementation demonstrates the most important heap operations for a Min Heap.

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 heap = new MinHeap();

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

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

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

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

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

JavaScript Max Heap Implementation

A Max Heap uses the same structural operations, but the comparison direction is reversed.

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

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

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

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

    const maximum = 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 largest = index;

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

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

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

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

      index = largest;
    }

    return maximum;
  }
}

const heap = new MaxHeap();

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

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

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

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

Min Heap vs Max Heap Operations

Operation	Min Heap	Max Heap
Root	Minimum	Maximum
Heapify up	Swap when child < parent	Swap when child > parent
Heapify down	Choose smaller child	Choose larger child
Root extraction	Extract minimum	Extract maximum
Peek	O(1)	O(1)
Insert	O(log n)	O(log n)
Extract root	O(log n)	O(log n)

Heap Operations and Priority Queues

One of the most important practical uses of heap operations is implementing a priority queue.

A priority queue repeatedly needs to process the highest- or lowest-priority item. A heap provides efficient insertion and removal while keeping the next priority item at the root.

Tasks:

Critical alert → 10
Send email     → 5
Generate report → 3

Max Heap:

        10
       /  \
      5    3

Extract Max → Critical alert

Heap Operations in Heap Sort

Heap operations also form the basis of Heap Sort. The algorithm first constructs a heap and then repeatedly extracts the root or moves the root to its final position.

Heap Sort has a time complexity of O(n log n).

Heapify Up vs Heapify Down

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

Common Heap Operation Mistakes

Forgetting to Remove the Last Element

During root extraction, the last element is moved to the root and must then be removed from its original position.

Choosing the Wrong Child

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

Assuming Build Heap Takes O(n log n)

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

Treating a Heap as a Sorted Structure

Heap operations guarantee the correct root and parent-child relationships, not a completely sorted array.

Using the Wrong Comparison

Min Heap and Max Heap operations use opposite comparison rules. Reversing the comparison can silently turn one heap type into the other or break the heap property.

When to Use Heap Operations

Heap operations are especially useful when an application repeatedly needs access to the smallest or largest item while new values are being added.

Priority queues
Task scheduling
Heap Sort
Dijkstra's algorithm
Finding the kth smallest or largest element
Top-k problems
Streaming data problems
Event scheduling
Resource prioritization

Heap Operation Complexity Summary

Operation	Time Complexity	Extra Space
Peek	O(1)	O(1)
Insert	O(log n)	O(1) auxiliary
Extract root	O(log n)	O(1) auxiliary
Heapify up	O(log n)	O(1) iterative
Heapify down	O(log n)	O(1) iterative
Build heap	O(n)	O(1) auxiliary for in-place construction
Search	O(n)	O(1) auxiliary for iterative search

Key Takeaways

Peek reads the root in O(1) time.
Insertion adds an element and restores order using heapify up.
Extracting the root removes the minimum or maximum element.
Heapify down restores the heap after root removal or replacement.
Both heapify up and heapify down take O(log n).
Bottom-up build heap takes O(n) time.
Building through repeated insertion takes O(n log n).
Searching for an arbitrary value can take O(n).
Min Heaps choose the smaller child during heapify down.
Max Heaps choose the larger child during heapify down.
Heap operations are fundamental to priority queues and Heap Sort.

Topics

Heap Operations: Insert, Delete and Peek