Heap Concept Structure and Properties in DSA Javascript - Execution Trace

Concept Flow - Heap Concept Structure and Properties

Start with empty heap

↓

Insert element at end of array

↓

Compare element with parent

↓

Swap with parent

↓

Repeat compare with new parent

↓

Stop when root reached or no swap needed

This flow shows how a heap maintains its structure by inserting elements at the end and bubbling them up by swapping with parents if needed.

Execution Sample

DSA Javascript

const heap = [];
heap.push(10);
heap.push(15);
heap.push(30);
heap.push(40);
heap.push(50);
heap.push(100);
heap.push(40);
heap.push(8);

This code inserts elements into a min-heap array and bubbles up the last inserted element to maintain heap property.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Insert 10	[10]	head=0	10
2	Insert 15	[10, 15]	head=0, new=1	10 \ 15
3	Insert 30	[10, 15, 30]	head=0, new=2	10 / \ 15 30
4	Insert 40	[10, 15, 30, 40]	new=3	10 / \ 15 30 / 40
5	Insert 50	[10, 15, 30, 40, 50]	new=4	10 / \ 15 30 / \ 40 50
6	Insert 100	[10, 15, 30, 40, 50, 100]	new=5	10 / \ 15 30 / \ / 40 50 100
7	Insert 40	[10, 15, 30, 40, 50, 100, 40]	new=6	10 / \ 15 30 / \ / \ 40 50 100 40
8	Insert 8	[10, 15, 30, 40, 50, 100, 40, 8]	new=7	10 / \ 15 30 / \ / \ 40 50 100 40 / 8
9	Bubble up 8 < 40? Swap	[10, 15, 30, 8, 50, 100, 40, 40]	swap indices 3 and 7	10 / \ 15 30 / \ / \ 8 50 100 40 / 40
10	Bubble up 8 < 15? Swap	[10, 8, 30, 15, 50, 100, 40, 40]	swap indices 1 and 3	10 / \ 8 30 / \ / \ 15 50 100 40 / 40
11	Bubble up 8 < 10? Swap	[8, 10, 30, 15, 50, 100, 40, 40]	swap indices 0 and 1	8 / \ 10 30 / \ / \ 15 50 100 40 / 40
12	Stop bubbling (root reached)	[8, 10, 30, 15, 50, 100, 40, 40]	no swap	8 / \ 10 30 / \ / \ 15 50 100 40 / 40

💡 Stop bubbling when inserted element reaches root or no parent is larger.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
heap array	[]	[10]	[10,15]	[10,15,30]	[10,15,30,40]	[10,15,30,40,50]	[10,15,30,40,50,100]	[10,15,30,40,50,100,40]	[10,15,30,40,50,100,40,8]	[10,15,30,8,50,100,40,40]	[10,8,30,15,50,100,40,40]	[8,10,30,15,50,100,40,40]	[8,10,30,15,50,100,40,40]
new element index	N/A	0	1	2	3	4	5	6	7	7->3	3->1	1->0	0
bubble up active	No	No	No	No	No	No	No	No	Yes	Yes	Yes	No	No

Key Moments - 3 Insights

Why do we insert the new element at the end of the array?

In the execution_table rows 1 to 8, the new element is always added at the end to maintain the complete binary tree structure before bubbling up.

Why do we compare the new element with its parent and swap?

As shown in rows 9 to 11, swapping with the parent ensures the heap property (parent smaller than children) is maintained by moving the smaller element up.

When does the bubbling up stop?

Row 12 shows bubbling stops when the element reaches the root or no parent is larger, so no more swaps are needed.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the array state after swapping?

A [8, 15, 30, 40, 50, 100, 40, 10]

B [10, 15, 30, 40, 50, 100, 40, 8]

C [10, 15, 30, 8, 50, 100, 40, 40]

D [10, 8, 30, 15, 50, 100, 40, 40]

💡 Hint

Check execution_table row 9 under 'Array State' column.

At which step does the new element reach the root of the heap?

A Step 10

B Step 11

C Step 9

D Step 12

💡 Hint

Look at variable_tracker for 'new element index' and see when it becomes 0.

If the inserted element was larger than its parent, what would happen in the bubbling steps?

A It would stop bubbling immediately.

B It would swap with the parent anyway.

C It would bubble down instead.

D It would be removed from the heap.

💡 Hint

Refer to concept_flow where bubbling stops if no swap needed.

Concept Snapshot

Heap is a complete binary tree stored as an array.
Insert new element at array end.
Bubble up by swapping with parent if smaller.
Stop when root reached or no swap needed.
Maintains min-heap property: parent ≤ children.

Full Transcript

A heap is a special tree structure stored as an array. When we add a new element, we put it at the end of the array to keep the tree complete. Then we compare it with its parent. If the new element is smaller, we swap them. We keep swapping up until the new element is no longer smaller than its parent or it reaches the root. This process keeps the heap property intact, where every parent is smaller or equal to its children. The execution table shows each insertion and bubbling step with the array and tree shape. The variable tracker follows the new element's position and the heap array after each step. Key moments explain why we insert at the end, why we swap, and when bubbling stops. The quiz tests understanding of array states and bubbling behavior. This visual trace helps beginners see how heaps keep order while staying complete trees.

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

Solution

1. Step 1: Understand max heap property

   A max heap requires that each parent node is greater than or equal to its children.

2. Step 2: Compare options with max heap definition

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

3. Final Answer:

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

4. Quick Check:

   Max heap = parent ≥ children [OK]

Hint: Max heap means parent is always bigger or equal [OK]

Common Mistakes:

• Confusing max heap with min heap property
• Thinking leaf nodes must be bigger than root
• Ignoring the complete binary tree requirement

2. Which of the following is the correct way to represent a heap in JavaScript using an array?

easy

A. Parent at index i, left child at i + 1, right child at i + 2

B. Parent at index i, left child at 2*i + 1, right child at 2*i + 2

C. Parent at index i, left child at 2*i, right child at 2*i + 1

D. Parent at index i, left child at i - 1, right child at i - 2

Solution

1. Step 1: Recall array indexing for heap

   In zero-based arrays, left child index = 2*i + 1, right child index = 2*i + 2.

2. Step 2: Match options with formula

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 matches the correct formula for zero-based indexing heaps.

3. Final Answer:

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 -> Option B

4. Quick Check:

   Heap array indexing = 2*i+1, 2*i+2 [OK]

Hint: Remember zero-based indexing: left=2i+1, right=2i+2 [OK]

Common Mistakes:

• Using one-based indexing formulas incorrectly
• Swapping left and right child indices
• Using i+1 or i+2 which is wrong for heap

3. Consider the following JavaScript code that builds a max heap from an array:

const arr = [3, 9, 2, 1, 4, 5];
function maxHeapify(arr, i, n) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    maxHeapify(arr, largest, n);
  }
}

function buildMaxHeap(arr) {
  let n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(arr, i, n);
  }
}

buildMaxHeap(arr);
console.log(arr);

What is the output printed?

medium

A. [3, 9, 2, 1, 4, 5]

B. [9, 3, 5, 1, 4, 2]

C. [5, 4, 3, 1, 9, 2]

D. [9, 4, 5, 1, 3, 2]

Solution

1. Step 1: Understand buildMaxHeap process

   Start heapifying from last non-leaf node at index 2 (value 2), then index 1 (value 9), then index 0 (value 3).

2. Step 2: Trace heapify calls

   Initial: [3,9,2,1,4,5]
   Heapify i=2: left=5 (5>2), largest=5, swap 2-5: [3,9,5,1,4,2]. Heapify 5: no children.
   Heapify i=1: left=3(1<9), right=4(4<9), no swap.
   Heapify i=0: left=1(9>3), largest=1; right=2(5<9), swap 0-1: [9,3,5,1,4,2]. Heapify 1 (val=3): left=3(1<3), right=4(4>3), largest=4, swap 1-4: [9,4,5,1,3,2]. Heapify 4: no children.

3. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option D

4. Quick Check:

   Max heap array after build = [9,4,5,1,3,2] [OK]

Hint: Heapify from bottom non-leaf nodes up [OK]

Common Mistakes:

• Not heapifying recursively after swap
• Confusing indices for children
• Assuming original array order remains

4. The following JavaScript function is intended to insert a new value into a max heap represented as an array. Identify the bug:

function insertHeap(arr, value) {
  arr.push(value);
  let i = arr.length - 1;
  while (i > 0) {
    let parent = Math.floor(i / 2);
    if (arr[parent] < arr[i]) {
      [arr[parent], arr[i]] = [arr[i], arr[parent]];
      i = parent;
    } else {
      break;
    }
  }
}

medium

A. Parent index calculation should be Math.floor((i - 1) / 2)

B. The loop should run while i >= 0

C. The swap should happen only if arr[parent] > arr[i]

D. The function should remove the last element before inserting

Solution

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

   In zero-based arrays, parent index = Math.floor((i - 1) / 2), not Math.floor(i / 2).

2. Step 2: Understand impact of wrong parent index

   Using Math.floor(i / 2) causes incorrect parent calculation, breaking heap property restoration.

3. Final Answer:

   Parent index calculation should be Math.floor((i - 1) / 2) -> Option A

4. Quick Check:

   Parent index = (i-1)//2 in zero-based heap [OK]

Hint: Parent index in zero-based heap = (i-1)//2 [OK]

Common Mistakes:

• Using i/2 instead of (i-1)/2 for parent
• Loop condition allowing i=0 to cause errors
• Swapping when parent is larger, not smaller

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

hard

A. [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 8, 10, 15, 20, 1] -> [1, 5, 8, 10, 15, 20, 2]

B. [2, 5, 8, 10, 15, 20, 1] -> [1, 5, 8, 10, 15, 20, 2]

C. [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 1, 10, 15, 20, 8] -> [1, 5, 2, 10, 15, 20, 8]

D. [2, 5, 8, 10, 15, 20, 1] -> [1, 2, 5, 10, 15, 20, 8]

Solution

1. Step 1: Insert value at end

   Insert 1 at the end: [2, 5, 8, 10, 15, 20, 1]

2. Step 2: Heapify up swaps

   Compare 1 with parent at index 2 (value 8), swap: [2, 5, 1, 10, 15, 20, 8]
   Compare 1 with new parent at index 0 (value 2), swap: [1, 5, 2, 10, 15, 20, 8]

3. Step 3: Final heap state

   Heap property restored with 1 at root.

4. Final Answer:

   [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 1, 10, 15, 20, 8] -> [1, 5, 2, 10, 15, 20, 8] -> Option C

5. Quick Check:

   Heapify up swaps child with parent until order restored [OK]

Hint: Heapify up swaps child with parent until order restored [OK]

Common Mistakes:

• Not swapping with correct parent index
• Stopping heapify too early
• Incorrect final heap array after swaps