DSA Javascriptprogramming

Heap Concept Structure and Properties in DSA Javascript

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

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 family tree where every parent is taller than their children, so the tallest person is always at the top, making it easy to find the tallest family member.

Dry Run Walkthrough

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

Goal: Rearrange the array into a max-heap where each parent is greater than its children

Step 1: Start from the last parent node at index 2 (value 8), compare with children and swap with largest child if needed

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

Why: We fix the subtree rooted at index 2 to satisfy max-heap property

Step 2: Move to parent node at index 1 (value 9), compare with children and swap if needed

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

Why: No swap needed because 9 is greater than children 4 and 7

Step 3: Move to root node at index 0 (value 5), compare with children and swap with largest child (10)

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

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

Step 4: Fix subtree rooted at index 2 (value 5), swap with largest child (8)

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

Why: After root swap, fix subtree to maintain max-heap

Result:

[10, 9, 8, 4, 7, 6, 5] -- max-heap formed

Annotated Code

DSA Javascript

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

  // Swap two elements in the heap array
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // Heapify subtree rooted at index i
  heapify(i) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

    // Check if left child is larger
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
      largest = left;
    }

    // Check if right child is larger
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
      largest = right;
    }

    // If largest is not root, swap and continue heapifying
    if (largest !== i) {
      this.swap(i, largest);
      this.heapify(largest);
    }
  }

  // Build max heap from array
  buildHeap(arr) {
    this.heap = arr.slice();
    const start = Math.floor(this.heap.length / 2) - 1;

    // Heapify from last parent to root
    for (let i = start; i >= 0; i--) {
      this.heapify(i);
    }
  }

  // Print heap as array
  printHeap() {
    console.log(this.heap);
  }
}

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

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

Check if left child is bigger than current largest

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

Check if right child is bigger than current largest

if (largest !== i) { this.swap(i, largest); this.heapify(largest); }

Swap with largest child and heapify subtree to maintain max-heap

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

Build heap by heapifying all parent nodes from bottom up

OutputSuccess

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

Complexity Analysis

Time: O(n) because heapify is called on all parent nodes and each heapify takes O(log n) but overall buildHeap is O(n)

Space: O(n) because we store the heap array of size n

vs Alternative: Building a heap by inserting elements one by one is O(n log n), so this bottom-up heapify is more efficient

Edge Cases

Empty array

Heap remains empty without errors

DSA Javascript

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

Single element array

Heap is the same single element

DSA Javascript

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

All elements equal

Heap remains unchanged as all parents equal children

DSA Javascript

if (this.heap[left] > 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, use a heap because it keeps the biggest or smallest at the top.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last parent node
Fix: Start heapify from Math.floor(n/2) - 1 to cover all parents

Mistake: Not recursively heapifying after swap
Fix: Call heapify again on the swapped child's index to fix subtree

Summary

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

Use a heap when you want fast access to the largest or smallest element in a collection.

The key is to fix the tree from bottom up so each parent is bigger than its children, making the top the biggest.

Practice

(1/5)

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

easy

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

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

C. All leaf nodes are greater than the root node

D. The tree is always a complete binary tree but unordered

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Heap Concept Structure and Properties in DSA Javascript

Practice

Solution

Step 1: Understand max heap property

Step 2: Compare options with max heap definition

Final Answer:

Quick Check:

Solution

Step 1: Recall array indexing for heap

Step 2: Match options with formula

Final Answer:

Quick Check:

Solution

Step 1: Understand buildMaxHeap process

Step 2: Trace heapify calls

Final Answer:

Quick Check:

Solution

Step 1: Check parent index formula in zero-based heap

Step 2: Understand impact of wrong parent index

Final Answer:

Quick Check:

Solution

Step 1: Insert value at end

Step 2: Heapify up swaps

Step 3: Final heap state

Final Answer:

Quick Check:

Ready to prove it?