Heap Concept Structure and Properties in DSA Typescript

Mental Model

A heap is a special tree where each parent is bigger (or smaller) than its children, making it easy to find the biggest or smallest item quickly.

Analogy: Imagine a pile of boxes stacked so that the biggest box is always on top, and every box below is smaller than the one above it.

       10
      /  \
     7    9
    / \  / \
   5  6 8  4

Array form: [10, 7, 9, 5, 6, 8, 4]

Dry Run Walkthrough

Input: Build a max heap from array: [5, 10, 4, 7, 6, 8, 9]

Goal: Rearrange the array so the largest value is at the root and each parent is larger than its children

Step 1: Start heapify from last parent node at index 2 (value 4)

[5, 10, 9, 7, 6, 8, 4]

Why: Swap 4 with larger child 9 to satisfy max heap property

Step 2: Heapify node at index 1 (value 10) - no change needed

[5, 10, 9, 7, 6, 8, 4]

Why: 10 is already larger than children 7 and 6

Step 3: Heapify root node at index 0 (value 5), swap with largest child 10

[10, 5, 9, 7, 6, 8, 4]

Why: Root must be largest, so swap 5 with 10

Step 4: Heapify node at index 1 (value 5), swap with largest child 7

[10, 7, 9, 5, 6, 8, 4]

Why: After root swap, fix subtree to maintain heap property

Result:

Final max heap array: [10, 7, 9, 5, 6, 8, 4]

Annotated Code

DSA Typescript

class MaxHeap {
  heap: number[];

  constructor(arr: number[]) {
    this.heap = arr;
    this.buildHeap();
  }

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

  heapify(i: number) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

    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 !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }

  printHeap() {
    console.log(this.heap.join(", "));
  }
}

const arr = [5, 10, 4, 7, 6, 8, 9];
const maxHeap = new MaxHeap(arr);
maxHeap.printHeap();

const startIdx = Math.floor(this.heap.length / 2) - 1;

Find last parent node to start heapify bottom-up

for (let i = startIdx; i >= 0; i--) { this.heapify(i); }

Heapify each parent node to build max heap

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

Check if left child is larger than current largest

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

Check if right child is larger than current largest

if (largest !== i) { swap and recurse heapify(largest); }

Swap parent with largest child and fix subtree

Output

10, 7, 9, 5, 6, 8, 4

Complexity Analysis

Time: O(n) because building a heap from an array requires heapifying nodes bottom-up, which is more efficient than repeated insertions

Space: O(1) because heapify is done in place without extra storage

vs Alternative: Naive approach inserting elements one by one into an empty heap costs O(n log n), slower than bottom-up heapify

Edge Cases

Empty array

Heap remains empty without errors

DSA Typescript

const startIdx = Math.floor(this.heap.length / 2) - 1;

Single element array

Heap is the single element itself, no swaps needed

DSA Typescript

for (let i = startIdx; i >= 0; i--) { this.heapify(i); }

All elements equal

Heap structure remains unchanged as all parents equal children

DSA Typescript

if (this.heap[left] > this.heap[largest]) and if (this.heap[right] > this.heap[largest])

When to Use This Pattern

When you need quick access to the largest or smallest item and want to maintain order efficiently, recognize the heap pattern because it organizes data in a tree with parent-child size rules.

Common Mistakes

Mistake: Starting heapify from the root instead of the last parent node
Fix: Start heapify from the last parent node at index floor(n/2)-1 and move upwards

Mistake: Not swapping parent with the largest child when heap property is violated
Fix: Always swap parent with the largest child and recursively heapify the affected subtree

Summary

A heap is a tree-based structure where parents are always larger (max heap) or smaller (min heap) than their children.

Use a heap when you need fast access to the largest or smallest element and efficient insertion or removal.

The key insight is that heapify from the bottom up fixes local violations to build a global heap efficiently.

Practice

1. What is a key property of a max-heap data structure?

easy

A. Every parent node is greater than or equal to its children

B. Every parent node is less than or equal to its children

C. All leaf nodes have the same value

D. The heap is always a complete binary tree with sorted leaves

Solution

1. Step 1: Understand max-heap property

   A max-heap requires each parent node to be greater than or equal to its children to maintain the heap order.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or incorrect properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option A

4. Quick Check:

   Max-heap property = Every parent ≥ children [OK]

Hint: Max-heap means parent ≥ children always [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaves must be sorted
• Assuming all leaf nodes have same value

2. Which of the following is the correct TypeScript syntax to declare a min-heap using an array?

easy

A. let minHeap = new Heap();

B. const minHeap: number[] = [];

C. const minHeap: Heap = new Heap();

D. var minHeap = [];

Solution

1. Step 1: Identify array declaration syntax in TypeScript

   Declaring an array of numbers uses syntax like const arr: number[] = [];.

2. Step 2: Check options for correct array declaration

   const minHeap: number[] = []; correctly declares an empty number array for min-heap storage. Others either use undefined Heap class or older syntax.

3. Final Answer:

   const minHeap: number[] = []; -> Option B

4. Quick Check:

   Array declaration with type = const arr: number[] = [] [OK]

Hint: Use const name: type[] = [] for array declaration [OK]

Common Mistakes:

• Using undefined Heap class without import
• Using var instead of const or let
• Missing type annotation in TypeScript

3. Given the following TypeScript code for a max-heap array representation:

const heap = [50, 30, 40, 10, 20];
console.log(heap[1]);

What will be the output?

medium

A. 10

B. 50

C. 40

D. 30

Solution

1. Step 1: Understand zero-based indexing in arrays

   Arrays in TypeScript start at index 0, so heap[0] = 50, heap[1] = 30.

2. Step 2: Identify value at index 1

   heap[1] accesses the second element, which is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   heap[1] = 30 [OK]

Hint: Array index starts at 0, so heap[1] is second element [OK]

Common Mistakes:

• Assuming heap indexing starts at 1
• Confusing value at index 0 with index 1
• Mixing up max-heap property with array indexing

4. Consider this TypeScript snippet to insert a value into a max-heap array:

const heap = [40, 30, 20];
heap.push(50);
// Missing code here to maintain heap property
console.log(heap);

Which code snippet correctly restores the max-heap property after insertion?

medium

A. heap.sort((a, b) => a - b);

B. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); }

C. while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); }

D. heap.reverse();

Solution

1. Step 1: Understand heapify-up process for max-heap

   After insertion, we compare the inserted node with its parent and swap if child is greater, repeating until heap property is restored.

2. Step 2: Analyze code snippets

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } correctly uses a while loop to swap child and parent if child is greater. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); } reverses condition (wrong for max-heap). Options A, B, and D do not maintain heap structure.

3. Final Answer:

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } -> Option C

4. Quick Check:

   Heapify-up swaps if child > parent [OK]

Hint: Swap up while child > parent to fix max-heap [OK]

Common Mistakes:

• Using wrong comparison direction in heapify-up
• Sorting array instead of heapifying
• Reversing array instead of fixing heap

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25]. You want to insert 12 and maintain the min-heap property. Which sequence of array states correctly shows the heap after insertion and heapify-up?

hard

A. [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15]

B. [5, 10, 15, 20, 25, 12] -> [5, 10, 15, 20, 25, 12]

C. [5, 10, 15, 20, 25, 12] -> [5, 12, 15, 20, 25, 10]

D. [5, 10, 15, 20, 25, 12] -> [12, 5, 15, 20, 25, 10]

Solution

1. Step 1: Insert 12 at the end of the array

   Initial array after insertion: [5, 10, 15, 20, 25, 12]

2. Step 2: Heapify-up to maintain min-heap

   Compare 12 with its parent 15 (index 2). Since 12 < 15, swap them. New array: [5, 10, 12, 20, 25, 15]. No further swaps needed as 12 > 10.

3. Final Answer:

   [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15] -> Option A

4. Quick Check:

   Heapify-up swaps child < parent in min-heap [OK]

Hint: Swap inserted value up while smaller than parent in min-heap [OK]

Common Mistakes:

• Not swapping inserted value with parent when smaller
• Assuming no change after insertion
• Swapping with wrong parent index