Max Heap Data Structure

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

What Is a Max Heap?

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

A Max Heap is useful when an application repeatedly needs access to the largest value. It is commonly used for priority queues, scheduling, Heap Sort, top-k problems, and algorithms that repeatedly select the maximum element. 

        50
       /  \
      30   40
     / \   /
    10 20 35

Every parent is greater than or equal to its children, and the root contains the maximum value: 50.

Max Heap Property

The defining rule of a Max Heap is:

Parent value ≥ Child value

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

Valid Max Heap:

        90
       /  \
      70   80
     / \   /
    40 60 50

The root contains the largest value, but the remaining elements do not have to be globally sorted.

Max Heap Is a Complete Binary Tree

A Max Heap must satisfy two properties: the complete binary tree property and the max heap property.

A complete binary tree has the following structure:

  • Every level is completely filled except possibly the last.
  • The last level is filled from left to right.
  • There are no gaps before another node on the same level.
        90
       /  \
      70   80
     / \
    40 60

This structural property allows the heap to be represented efficiently using an array.

Max Heap Array Representation

A Max Heap is usually implemented using an array. Consider: 

        90
       /  \
      70   80
     / \   /
    40 60 50

Its array representation is: 

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

With zero-based indexing, the relationships between array positions 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

Accessing the Maximum Element

The maximum element is always at index 0. Reading it without removing it is called peek. 

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

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

Because the root directly stores the largest element, the peek operation takes O(1) time.

Inserting an Element into a Max Heap

When a new element is inserted, it is first added to the end of the array. This preserves the complete-tree structure.

The new value is then compared with its parent. If it is larger than its parent, they are swapped. This continues until the Max Heap property is restored. This process is called heapify up or sift up.

Insertion Example

Start with: 

        50
       /  \
      40   30
     / \
    20 10

Insert 60 at the next available position: 

        50
       /  \
      40   30
     / \  /
    20 10 60

Since 60 is greater than its parent 30, swap them: 

        50
       /  \
      40   60
     / \  /
    20 10 30

The value 60 is still greater than its parent 50, so another swap is performed: 

        60
       /  \
      40   50
     / \  /
    20 10 30

The Max Heap property has now been restored.

Max Heap Insertion Algorithm

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

Removing the Maximum Element

Since the largest element is always at the root, removing the maximum means removing the root element.

The usual extraction process is:

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

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

Example of Extracting the Maximum

Consider the following Max Heap: 

        90
       /  \
      70   80
     / \   /
    40 60 50

Remove 90. Move the last element, 50, to the root: 

        50
       /  \
      70   80
     / \
    40 60

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

        80
       /  \
      70   50
     / \
    40 60

The Max Heap property has been restored.

Why Does Heapify Down Choose the Larger Child?

In a Max Heap, the parent must be greater than or equal to both children. If the current node is smaller than both children, it must move above the larger child. 

        30
       /  \
      50   80

The correct swap is with 80, because after the swap: 

        80
       /  \
      50   30

The parent-child ordering is preserved.

Building a Max Heap from an Array

An existing array can be transformed into a Max Heap using bottom-up heap construction. The process starts with the last non-leaf node and performs heapify down toward the root. 

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

// One valid Max Heap representation:
//
// [40, 15, 30, 5, 10, 20]

A heap is not required to be sorted. The resulting array only needs to satisfy the Max Heap property.

Max Heap Implementation in JavaScript

A Max Heap can be implemented using an array and a small set of helper operations. 

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;
    }
  }

  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 maxHeap = new MaxHeap();

maxHeap.insert(30);
maxHeap.insert(10);
maxHeap.insert(50);
maxHeap.insert(20);
maxHeap.insert(40);

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

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

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

console.log(maxHeap.peek());
// 40

Max Heap Time Complexity

Operation Complexity Reason
Peek maximum O(1) Maximum is always at the root
Insert O(log n) Element may move up the heap
Extract maximum 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

Max Heap Space Complexity

A Max Heap containing n elements requires O(n) storage. When represented using an array, the heap does not need separate objects for each parent-child reference.

Max Heap vs Min Heap

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

Max Heap vs Sorted Array

A sorted array maintains a complete ordering between its elements, while a Max Heap only guarantees the parent-child relationship.

This difference allows a Max Heap to efficiently maintain the largest element while supporting dynamic insertion and maximum extraction.

Operation Max Heap Sorted Array
Get maximum O(1) O(1)
Insert O(log n) O(n) typically
Extract maximum O(log n) Depends on representation
Arbitrary search O(n) O(log n) with binary search

Max Heap and Priority Queues

A Max Heap can implement a priority queue where the item with the highest priority is processed first. 

const tasks = [
  { name: "Generate report", priority: 3 },
  { name: "Critical alert", priority: 10 },
  { name: "Send email", priority: 5 }
];

// A Max Heap ordered by priority would process:
//
// Critical alert      → priority 10
// Send email          → priority 5
// Generate report     → priority 3

The maximum-priority task remains accessible at the root.

Applications of Max Heap

Max Heaps are useful when the largest value or highest-priority item needs to be retrieved repeatedly.

  • Maximum-priority queues.
  • Task scheduling.
  • Heap Sort.
  • Finding the kth largest element.
  • Top-k problems.
  • Maintaining the largest values in a data stream.
  • Resource prioritization.
  • Event processing based on priority.

Max Heap in Heap Sort

Max Heap is closely associated with Heap Sort. A max heap can be used to repeatedly move the largest remaining value to its final position.

Heap Sort has a time complexity of O(n log n). When implemented in-place, it can perform the sorting using O(1) auxiliary space apart from the input array.

Finding the Kth Largest Element

A Max Heap can repeatedly extract the maximum value. Extracting the maximum k times can identify the kth largest element. 

Values:

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

Largest:
90

2nd largest:
70

3rd largest:
60

In practical problems, a heap is often combined with additional techniques so that only the required number of elements needs to be maintained.

Max Heap for Top-K Problems

Many applications need the largest few values rather than a completely sorted collection. Heap-based approaches can avoid sorting every value when only a small number of top elements are required.

Examples include:

  • Top 10 products by sales.
  • Top 5 highest scores.
  • Highest-priority tasks.
  • Largest transaction amounts.
  • Most valuable items in a stream.

Common Max Heap Mistakes

Thinking the Heap Is Fully Sorted

A Max Heap does not sort all elements. It only guarantees that every parent is greater than or equal to its children.

Searching for an Arbitrary Value in O(log n)

A Max Heap is optimized for the maximum element. It does not provide the ordering needed for efficient arbitrary-value search, so searching can take O(n).

Choosing the Wrong Child During Heapify Down

When restoring a Max Heap from the root downward, the larger child should be selected when both children need to be considered.

Confusing Max Heap with Binary Search Tree

A Max Heap only guarantees a parent-child relationship. A Binary Search Tree organizes values relative to the root and its subtrees, which provides a different type of ordering.

Max Heap Operation Summary

Operation Description Time
Peek Read the maximum element O(1)
Insert Add an element and heapify up O(log n)
Extract Max 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 Max Heap is a complete binary tree.
  • Every parent is greater than or equal to its children.
  • The largest element is always at the root.
  • Max Heaps are commonly represented using arrays.
  • Peek returns the maximum in O(1) time.
  • Insertion uses heapify up and takes O(log n).
  • Extracting the maximum 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).
  • Max Heaps are useful for priority queues, Heap Sort, and top-k problems.

Code Examples 

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
    
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;
    }
  }

  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.extractMax());
// 50

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

  // Build Max Heap.
  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(
  kthLargest([8, 3, 10, 2, 7, 5], 3)
);
// 7

Pro Tip

Use a Max Heap when the largest or highest-priority item must remain quickly accessible while values are continuously inserted and removed. Remember the core pattern: O(1) peek, O(log n) insert, and O(log n) extract-max.

🎨 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.