Heap Concept Structure and Properties in DSA Typescript - Execution Trace

Concept Flow - Heap Concept Structure and Properties

Start with empty heap

↓

Insert element at end of array

↓

Compare element with parent

Yes / No↓

Swap with parent

↓

Repeat compare with new parent

↓

Heap property maintained

↓

Heap ready for next operation

This flow shows how elements are added to a heap and moved up to maintain the heap property.

Execution Sample

DSA Typescript

Insert 10
Insert 15
Insert 30
Insert 40
Insert 50
Insert 100

Inserting elements one by one into a min-heap and adjusting to maintain heap property.

Execution Table

Step	Operation	Nodes in Heap (Array)	Pointer Changes	Visual State (Tree)
1	Insert 10	[10]	head=0	10
2	Insert 15	[10, 15]	Compare 15 with parent 10: 15 > 10, no swap	10 / 15
3	Insert 30	[10, 15, 30]	Compare 30 with parent 10: 30 > 10, no swap	10 / \ 15 30
4	Insert 40	[10, 15, 30, 40]	Compare 40 with parent 15: 40 > 15, no swap	10 / \ 15 30 / 40
5	Insert 50	[10, 15, 30, 40, 50]	Compare 50 with parent 15: 50 > 15, no swap	10 / \ 15 30 / \ 40 50
6	Insert 100	[10, 15, 30, 40, 50, 100]	Compare 100 with parent 30: 100 > 30, no swap	10 / \ 15 30 / \ / 40 50 100
7	End	[10, 15, 30, 40, 50, 100]	Heap property maintained, no more swaps	Final heap as above

💡 All elements inserted and heap property maintained after each insertion.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	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]
Last Inserted Index	N/A	0	1	2	3	4	5	5
Parent Index	N/A	N/A	0	0	1	1	2	N/A
Swaps Made	0	0	0	0	0	0	0	0

Key Moments - 3 Insights

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

Because the heap is a complete binary tree, new elements are always added at the next available leaf position, which corresponds to the end of the array (see execution_table steps 1 to 6).

Why do we compare the inserted element with its parent?

To maintain the heap property (min-heap here), the inserted element must be smaller than or equal to its parent. If not, we swap and continue up (execution_table shows no swaps because all inserted elements are larger).

What happens if the inserted element is larger than its parent?

No swap is needed and the heap property is maintained immediately (see steps 2 to 6 in execution_table where no swaps occur).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the parent index of the newly inserted element?

A 0

B 1

C 3

D 2

💡 Hint

Check the 'Parent Index' column in variable_tracker after step 4.

At which step does the heap first have 5 elements?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Nodes in Heap (Array)' column in execution_table to count elements.

If we inserted 5 instead of 50 at step 5, what would happen?

A Swap with parent 15, then swap with 10

B No swap, 5 stays at the end

C Swap with 30 only

D Heap property breaks

💡 Hint

Recall heap property and bubbling up process from concept_flow and execution_table.

Concept Snapshot

Heap is a complete binary tree stored as an array.
Insertions add element at array end.
Compare inserted element with parent.
Swap if smaller (min-heap) to maintain heap property.
Repeat until heap property holds.
No swaps if inserted element is larger than parent.

Full Transcript

A heap is a special tree structure where every parent node is smaller than its children in a min-heap. We add new elements at the end of the array to keep the tree complete. Then we compare the new element with its parent. If the new element is smaller, we swap and continue moving up until the heap property is restored. If the new element is larger, no swaps are needed. This process keeps the heap balanced and ordered for efficient access.

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