Heaps Demystified

Introduction

let’s start with what is complete binary tree and full binary tree.

Complete Binary Tree:

A Complete Binary Tree is one in which, during level order traversal, there are no missing nodes.
All levels are completely filled except possibly the last level, which is filled from left to right.

In other words:

A complete binary tree is a type of binary tree with specific structural properties. These properties are:

All levels are completely filled, except possibly the last level.This means that every level of the tree, from the root down to the second-to-last level, must contain the maximum possible number of nodes for that level. For example: level 0 (the root) has 1 node, level 1 has 2 nodes, level 2 has 4 nodes, and so on.

Nodes at the last level are as far left as possible.If the last level is not completely filled, the nodes present in that level must be arranged contiguously from the left side, with no gaps. There cannot be a right child without a corresponding left child at the same level.

In simpler terms, a complete binary tree looks like a perfectly filled binary tree,Except that the bottom-most row might have some empty spots, but only on the right side. This structure ensures compact and efficient representation, often used in data structures like heaps.

Source: Internet

Full Binary Tree:

Every full binary tree is always a complete binary tree.
At every level, all the nodes are present.
You need to fill all the nodes at each level before moving to the next.
The number of nodes at each level is 2n; n is the level number (starting from 0).

Heap and types:

A Heap is a complete binary tree data structure that satisfies the heap property. Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.

Based on heap property, there are two types of heaps

Min Heap:

All the parent(value) should be less than or equal (<=) to children’s
Smallest element on the root.

Max Heap:

All the parent(value) should be greater than or equal (>=) to children’s
Largest element on the root.

Advantages

Max Heap: If we have to find largest elements inside maxHeap: Time Complexity: O(1) Because it always on root, return root.val
Insert: O(logn)
Delete: O(logn)
Min Heap: If we have to find smallest elements inside minHeap: Time Complexity: O(1)
search in Heap:Time Complexity: O(nlogn)

Disadvantages

Slightly tricky to code.
Lack of Flexibility.

Array representation of Heap:

We can use arrays to represent a heap.
We can also represent heap using pointers or references.

Let’s see a Binary Tree representation using an Array

All the empty spaces are represented by '#'

MinHeap Representation

Using Level Order traversal

arr[0] or heap[0] is the smallest element
the time complexity for the smallest element is O(1)

MaxHeap Representation

arr[0] or heap[0] is the largest element
the time complexity for the largest element is O(1)

Traversing between child or parent nodes in an array representation

Formula’s based on index 1

left = 2 * i
right = 2 * i + 1
parent = floor(i / 2)

Formula’s based on index 0

left = 2 * i + 1
right = 2 * i + 2
parent = floor ((i – 1)÷2)

Understanding Operations in Heap

Insert
- We need to make sure that we follow these two rules:
  - Complete Binary Tree
  - Parent value <= children
Extract / Delete
- Only Extract (delete) from the root/top/front.
- In minHeap: The minimum value will be extracted from the heap.
- In maxHeap: The maximum value will be extracted from the heap.
Peek: This also happens at top.

Inserting Elements into a Heap

Steps:

Add element at end
Heapify the last index to top, means heapify up

Always ensure that your heap is a complete binary tree.
And maintain heap property, for Minheap all Parent <= Children

HeapifyUp

The process of moving these values up and maintaining the property of heap is known as Heapify. Basically, restructuring or rearranging the elements inside the binary tree so that it becomes a Heap.

🧑‍💻 Code:

⚙️ Key Methods

getLeftIndex(i) → 2*i + 1
getRightIndex(i) → 2*i + 2
getParentIndex(i) → Math.floor((i - 1) / 2)

🧩 Insert Logic

Add element at end of array.
Heapify Up — compare with parent,
- if smaller → swap and move up until heap property holds.

📘 Code Flow

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

    getLeftIndex(i) {
        return 2 * i + 1;
    }

    getRightIndex(i) {
        return 2 * i + 2;
    }

    getParentIndex(i) {
        return Math.floor((i - 1) / 2);
    }

    insert(val) {
        this.heap.push(val);
        let lastIndex = this.heap.length - 1;
        this.heapifyup(lastIndex);
    }

    heapifyup(i) {
        while (i > 0) {
            let parentIndex = this.getParentIndex(i);
            if (this.heap[parentIndex] > this.heap[i]) {
                [this.heap[parentIndex], this.heap[i]] =
                    [this.heap[i], this.heap[parentIndex]];
                i = parentIndex
            }
            else break
        }
    }
}

let myArr = new MinHeap();

myArr.insert(30);
myArr.insert(20);
myArr.insert(10);
myArr.insert(50);
myArr.insert(5);
myArr.insert(1);
myArr.insert(0);

console.log(myArr.heap);

⏱️ Time & Space

Insert: O(log N) (due to heapify-up)
Space: O(N)

💡 Example Output

After inserting [30, 20, 10, 50, 5, 1, 0]

👉 heap = [0, 5, 1, 50, 30, 10, 20] (min at root)

Extract / Deletion

🧠 Concept

MinHeap maintains the smallest element at the top.

heapifyUp: ensures order when inserting (bubble up).
heapifyDown: ensures order when deleting (bubble down).
extract(): removes and returns the minimum element (root).

⚙️ Insert → heapifyUp()

When a new element is added at the end,
Compare it with its parent → if smaller → swap → repeat upward.

🧩 heapifyUp()

heapifyup(i) {
  while (i > 0) {
    let p = this.getParentIndex(i);
    if (this.heap[p] > this.heap[i]) {
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    } else break;
  }
}

Purpose: Fix the heap after insertion (bubble up).

Time: O(log N)

⚙️ Extract (Delete Min)

Steps:

Root (min) = smallest element.
Swap root with last element.
Remove the last element.
Call heapifyDown(0) to restore the heap property.

🧩 extract()

extract() {
  if (this.heap.length < 1) return null;
  let min = this.heap[0];
  let last = this.heap.length - 1;
  [this.heap[0], this.heap[last]] = [this.heap[last], this.heap[0]];
  this.heap.pop();
  this.heapifyDown(0);
  return min;
}

Purpose: Remove the smallest value while maintaining heap structure.

Time: O(log N)

⚙️ Restore Order → heapifyDown()

When the last element replaces the root:

Compare it with its children → if greater than the smallest child → swap → continue downward.

🧩 heapifyDown()

heapifyDown(i) {
  let n = this.heap.length;
  let smallest = i;

  let left = this.getLeftIndex(i);
  let right = this.getRightIndex(i);

  if (left < n && this.heap[left] < this.heap[smallest])
    smallest = left;

  if (right < n && this.heap[right] < this.heap[smallest])
    smallest = right;

  if (smallest !== i) {
    [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
    this.heapifyDown(smallest);
  }
}

Purpose: Fix the heap after deletion (bubble down).

Time: O(log N)

💡 Example Flow

Insert → [30,20,10,50,5,1,0] → heap = [0,5,1,50,30,10,20]

Extract → removes 0, next heap = [1,5,10,50,30,20]

To complete the MinHeap class, we can add:

peek() → view smallest element without removing it.
buildHeap(array) → efficiently convert an array into a valid min-heap.

Both make the heap more practical for real-world use (like priority queues).

⚙️ peek()

Simply returns the root element (heap[0]) — smallest value — without modifying the heap.

📘 Code

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

Time: O(1)

💡 Usage

myHeap.peek(); // returns min element

⚙️ buildHeap(array)

Instead of inserting elements one by one (O(N log N)),

We can heapify all non-leaf nodes from bottom up — O(N) time.

📘 Code

buildHeap(arr) {
  this.heap = arr;
  let startIdx = Math.floor(this.heap.length / 2) - 1;
  for (let i = startIdx; i >= 0; i--) {
    this.heapifyDown(i);
  }
}

Logic:

Start from last non-leaf node → Math.floor(n/2) - 1.
Call heapifyDown() for each node upward.
By the time we reach the root, the heap property holds for all nodes.

Time: O(N)

⚙️ Final Class (Complete MinHeap)

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

  getLeftIndex(i) { return 2 * i + 1; }
  getRightIndex(i) { return 2 * i + 2; }
  getParentIndex(i) { 
      return Math.floor((i - 1) / 2); 
  }

  insert(val) {
    this.heap.push(val);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(i) {
    while (i > 0) {
      let p = this.getParentIndex(i);
      if (this.heap[p] > this.heap[i]) {
        [this.heap[p], this.heap[i]] =  
           [this.heap[i], this.heap[p]];
        i = p;
      } else break;
    }
  }

  extract() {
    if (this.heap.length < 1) return null;
    let min = this.heap[0];
    let last = this.heap.length - 1;
    [this.heap[0], this.heap[last]] = 
       [this.heap[last], this.heap[0]];
    this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  heapifyDown(i) {
    let n = this.heap.length;
    let smallest = i;
    let left = this.getLeftIndex(i);
    let right = this.getRightIndex(i);

    if (left < n && 
        this.heap[left] < this.heap[smallest])
      smallest = left;
    if (right < n && 
       this.heap[right] < this.heap[smallest])
      smallest = right;

    if (smallest !== i) {
      [this.heap[i], this.heap[smallest]] = 
          [this.heap[smallest], this.heap[i]];
      this.heapifyDown(smallest);
    }
  }

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

  buildHeap(arr) {
    this.heap = arr;
    let startIdx = Math.floor(this.heap.length / 2) - 1;
    for (let i = startIdx; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }
}

💡 Example Usage

let heap = new MinHeap();
heap.buildHeap([10, 50, 20, 5, 30, 2]);
console.log(heap.heap);   //[2, 5, 10, 50, 30, 20]
console.log(heap.peek()); // 2
console.log(heap.extract()); // 2
console.log(heap.heap);   // [5, 20, 10, 50, 30]

⏱️ Summary

Method	Purpose	Time	Space	Notes
insert	Add new element	O(log N)	O(1)	Heapify up
extract	Remove smallest	O(log N)	O(1)	Heapify down
peek	View smallest	O(1)	O(1)	No modification
buildHeap	Bulk heap creation	O(N)	O(1)	Efficient construction

Q)Why do we use heapify down in build heap? Why not heapify up?

When we call buildHeap(arr), we already have all elements placed in the array, We just need to reorganise them to satisfy the heap property:

For a MinHeap → every parent ≤ its children.

Now, the violation, if any, always happens downward —

because parent elements might be larger than their children.

That’s why we fix the heap from top to bottom → using heapifyDown().

⚙️ Visual Intuition

Say we start with an array:

[10, 50, 20, 5, 30, 2]

Represented as a tree:

We start from the last non-leaf node (index = n/2 – 1).

Here, that’s 50 (index 1).

Now, for each node:

Its children might violate the heap rule.
So we call heapifyDown(i) to push it down to the correct place.

By the time we reach the root (i = 0):

Every subtree below is already a valid min-heap.

🧩 Why not heapifyUp()?

If we used heapifyUp() from the bottom:

Each leaf would try to bubble up individually.
That means O(log n) work per node → total O(n log n) time.
This is basically the same as inserting elements one by one.

heapifyDown() from middle to top:

Each node only moves down as far as needed.
Total work = O(n), because deeper nodes are cheaper to fix.

So:

✅ heapifyDown → O(n) efficient build

❌ heapifyUp → O(n log n) slower build

Operation	Used in	Complexity	Why
heapifyUp	Insertion	O(log n)	Fix single new element
heapifyDown	Build/Extract	O(n )	Fix subtree violations

💬 Summary Thought

We use heapifyDown() in buildHeap()

because we’re building from existing elements downward, not inserting one by one.

It’s what makes heap construction linear time O(N) instead of O(N log N).

MaxHeap : (full code)

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

    getLeftIndex(i) { return 2 * i + 1}
    getRightIndex(i) { return 2* i + 2}
    getParentIndex(i) { 
        return Math.floor((i-1)/2)
    }

    insert(val) {
        this.heap.push(val)
        let lastIndex = this.heap.length - 1
        this.heapifyUp(lastIndex)
    }

    heapifyUp(i) {
        while (i > 0){
            let parentIndex = this.getParentIndex(i)
            if ( this.heap[parentIndex] < this.heap[i]){
                [this.heap[parentIndex], this.heap[i]] =
                     [this.heap[i], this.heap[parentIndex]]
                i = parentIndex
            }
            else break
        }
    }

    extract() {
        if (this.heap.length === 0) return null;
        let max = this.heap[0];
        let lastIndex = this.heap.length -1;
        [this.heap[0] , this.heap[lastIndex]] =
             [this.heap[lastIndex], this.heap[0]];
        this.heap.pop();
        this.heapifyDown(0)
        return max;
    }
    
    heapifyDown(i){
        let n = this.heap.length
        let max  = i;
        let leftIndex = this.getLeftIndex(i)
        let rightIndex = this.getRightIndex(i)

        if (leftIndex < n &&  this.heap[leftIndex] > this.heap[max]){
            max = leftIndex
        }
        if (rightIndex < n && this.heap[rightIndex] > this.heap[max]){
            max = rightIndex
        }

        if (max != i){
            [this.heap[i], this.heap[max]] = 
                [this.heap[max], this.heap[i]]
            this.heapifyDown(max)
        }
        
    }

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

    buildHeap(arr) {
        this.heap = arr;
        // Start heapifying from the last non-leaf node
        let startIdx = Math.floor(this.heap.length / 2) - 1;
        for (let i = startIdx; i >= 0; i--) {
            this.heapifyDown(i);
        }
    }
}

let myArr = new MaxHeap();

myArr.insert(30);
myArr.insert(20);
myArr.insert(10);
myArr.insert(50);
myArr.insert(5);
myArr.insert(1);
myArr.insert(0);
myArr.insert(55);
myArr.insert(40);
console.log(myArr.heap);
console.log(myArr.extract());
console.log(myArr.heap);
console.log(myArr.extract());

console.log(myArr.heap);

Heapsort

Heap Sort sorts an array by:

Building a Max-Heap (parent ≥ children).
Repeatedly swapping the root (maximum) with the last element.
Shrinking the heap size and fixing the heap with heapify.

Pros: In-place, comparison-based, no extra array used.

⚙ Algorithm Steps

Build Max-Heap
- Start heapifying from the last non-leaf node: floor(n/2) – 1 down to 0.
- Use heapifyDown to ensure subtree rooted at i satisfies max-heap property.
Extract Max and Place at End
- For i from n-1 down to 1:
  - Swap arr[0] (max) with arr[i].
  - Heapify the reduced heap [0…i-1] to restore max-heap.
heapifyDown Details
- Compute children: left = 2i + 1, right = 2i + 2.
- Find largest among i, left, right (within heap size n).
- If largest ≠ i, swap and recurse on largest.

🧩 Correctness Intuition

Max-Heap guarantees the root is the largest element.
After each swap, the placed element at the end is final.
Heapify reestablishes the heap for remaining elements, ensuring the next root is the next-largest.

⏱ Time & Space

Build-heap: O(n log n) ⇒ O(n) as O (log n) is negligible
Intuition
- Not every heapify costs log n. Nodes near the bottom have very small height, so their percolation distance is short.
- We only start heapifying from the last non-leaf up to the root; most of these nodes are low height.
- Aggregate work is the sum over all nodes of “height of the node,” which sums to O(n).
Each extraction: O(log n), repeated n times → O(n log n).
Total: O(n log n) time worst/avg/best.
Space: O(1) extra (in-place), but recursive heapify uses O(log n) call stack; iterative heapify removes this.

💡 Properties & Notes

Not stable (equal elements may change relative order).
Good for in-place sorting when memory is tight.
Predictable O(n log n) even for sorted input (unlike quicksort’s worst-case).
Cache behavior worse than quicksort/mergesort in practice due to pointer-like jumps.

🔍 Walkthrough on a small example

Input: [4, 1, 3, 2]
Build max-heap → [4, 2, 3, 1]
Swap root with last → [1, 2, 3, 4], heapify [0..2] → [3, 2, 1, 4]
Swap root with index 2 → [1, 2, 3, 4], heapify [0..1] → [2, 1, 3, 4]
Swap root with index 1 → [1, 2, 3, 4] → done

// heapSort.js
function heapSort(arr) {
    let n = arr.length;

    // Build Max-Heap: start from last non-leaf node
    let startIdx = Math.floor(n / 2) - 1;
    for (let i = startIdx; i >= 0; i--) {
        heapifyDownIter(arr, i, n);
    }

    // Extract max and rebuild heap
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        // heap size shrinks to i
        heapifyDownIter(arr, 0, i); 
    }
    return arr;
}

// Iterative heapify to avoid recursion stack usage
function heapifyDownIter(arr, i, n) {
    while (true) {
        let max = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;

        if (left < n && arr[left] > arr[max]) {
            max = left;
        }
        if (right < n && arr[right] > arr[max]) {
            max = right;
        }

        if (max === i) break;

        [arr[i], arr[max]] = [arr[max], arr[i]];
        i = max; // continue percolating down
    }
}

// Example
let arr = [2, 5, 1, 40, 25, 30, 4, 100, 45, 25, 3];
console.log(heapSort(arr)); // [1, 2, 3, 4, 5, 25, 25, 30, 40, 45, 100]

🧪 Edge Cases

Empty array or single element → already sorted.
All equal elements → no swaps after build-heap; still not stable.
Very large arrays → prefer iterative heapify to avoid recursion depth issue

heapify code with `recursion stack usage`

function heapSort(arr) {
    let n = arr.length;
    // create MaxHeap from arr
    // We don't need to build for leaf nodes
    let startIdx = Math.floor((n/2)-1);
    for (i = startIdx; i>=0; i--){
        heapifyDown(arr, i, n)
    }
    
    // sort the array
    for (i = n-1; i > 0; i--){
        // swap first and last value
        [arr[0], arr[i]] =[arr[i], arr[0]]
        heapifyDown(arr,0,i)
    }
    return arr
}

function heapifyDown(arr, i, n) {
    let max  = i;
    let leftIndex = 2 * i + 1
    let rightIndex = 2 * i + 2

    if (leftIndex < n && arr[leftIndex] > arr[max]){
        max = leftIndex
    }
    if (rightIndex <n && arr[rightIndex] > arr[max]){
        max= rightIndex
    }
    if(max != i){
        [arr[max], arr[i]] = [arr[i], arr[max]]
        heapifyDown(arr, max, n) 
    }

}

Comparison of various sorting algorithms:

Sorting Algorithm	Best TC	Average TC	Worst TC	SC	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Tim	O(n)	O(n log n)	O(nlogn)	O(n)	Yes
Shell	O(n log n)	–	O(n²)	O(1)	No
Intro	O(n log n)	O(n log n)	O(n log n)	O(log n)	No

What is stability in sorting algorithms, and when to consider?

Stability means equal keys keep their original relative order after sorting.

A sorting algorithm is called stable if, when two elements are compared as equal, it preserves the order they appeared in the input. This matters when elements carry extra data beyond the key you sort on. For example, if you sort employees by salary, a stable sort keeps employees with the same salary in their original sequence, so a later sort by department or name can rely on that ordering.

Stable examples: Insertion sort, Merge sort, Timsort, Counting/Radix sort.
Unstable examples: Quick sort, Heap sort, Selection sort (unless specially modified).

Practically, choose stability when:

You do multi-pass sorts on different keys.
You need predictable grouping of equals.
You’re sorting records with metadata and want non-key order preserved.

I am Harisai