Heap Concept Structure and Properties in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a heap in data structures?

A heap is a special tree-based data structure that satisfies the heap property: in a max heap, every parent node is greater than or equal to its children; in a min heap, every parent node is less than or equal to its children.

beginner

What is the difference between a max heap and a min heap?

A max heap has the largest element at the root, with each parent node greater than or equal to its children. A min heap has the smallest element at the root, with each parent node less than or equal to its children.

intermediate

How is a heap usually represented in memory?

A heap is usually represented as an array where the parent and child relationships are determined by indices: for a node at index i, its left child is at 2i + 1, and its right child is at 2i + 2.

beginner

What is the heap property?

The heap property ensures that in a max heap, every parent node is greater than or equal to its children, and in a min heap, every parent node is less than or equal to its children. This property must hold for all nodes except leaves.

intermediate

Why is a heap considered a complete binary tree?

A heap is a complete binary tree because all levels are fully filled except possibly the last level, which is filled from left to right without gaps. This structure allows efficient storage in arrays.

In a max heap, where is the largest element located?

A At any random node

B At the root node

C At the rightmost leaf

D At the leftmost leaf

In a max heap, the largest element is always at the root node because every parent is greater than or equal to its children.

How do you find the left child index of a node at index i in a heap array?

A 2 * i + 1

B 2 * i

C i / 2

D i + 1

The left child of a node at index i is at index 2 * i + 1 in the array representation of a heap.

What type of tree structure is a heap?

A Perfect binary tree

B Full binary tree

C Complete binary tree

D Binary search tree

A heap is a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right.

Which property must a min heap satisfy?

A Parent nodes are less than or equal to their children

B Parent nodes are greater than their children

C All leaf nodes are greater than root

D Children nodes are always equal

In a min heap, every parent node is less than or equal to its children, ensuring the smallest element is at the root.

Why is a heap efficient for implementing priority queues?

A Because it uses linked lists internally

B Because it stores elements in sorted order

C Because it has no structure

D Because it allows quick access to the highest or lowest priority element

Heaps allow quick access to the highest (max heap) or lowest (min heap) priority element at the root, making them efficient for priority queues.

Explain the structure and key properties of a heap.

Think about how the tree is filled and how parent and child values relate.

Describe how you can find the children and parent of a node in a heap stored as an array.

Use simple math formulas based on the node's index.

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