Heap Concept Structure and Properties in DSA C - 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 shape property of a heap?

The shape property means the heap is a complete binary tree, which means all levels are fully filled except possibly the last level, which is filled from left to right.

beginner

Explain the heap property in simple terms.

The heap property ensures that the parent node is always bigger (max heap) or smaller (min heap) than its children, so the root node is always the largest or smallest element.

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, left child is at 2*i + 1, right child at 2*i + 2, and parent at (i-1)/2.

intermediate

Why is the heap structure useful for priority queues?

Because the heap property keeps the highest (or lowest) priority element at the root, it allows quick access, insertion, and removal of the priority element, making it efficient for priority queues.

What does the shape property of a heap ensure?

A The tree is balanced like AVL

B All nodes have two children

C The heap is a complete binary tree

D The root is always the smallest element

The shape property means the heap is a complete binary tree, fully filled except possibly the last level filled from left to right.

In a max heap, what is true about the parent and child nodes?

A Parent is smaller than children

B Parent is equal or larger than children

C Parent is always the smallest node

D Children are always larger than parent

In a max heap, every parent node is greater than or equal to its children.

How is the left child index calculated in an array representation of a heap?

A 2*i + 1

B i/2

C 2*i

D i - 1

For a node at index i, the left child is at index 2*i + 1.

What is the root node in a min heap?

A The smallest element

B The last inserted element

C The middle element

D The largest element

In a min heap, the root node is the smallest element.

Why is a heap efficient for implementing priority queues?

A Because it stores elements in sorted order

B Because it balances like a binary search tree

C Because it uses linked lists

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

Heap keeps the highest or lowest priority element at the root, allowing quick access and efficient insertion/removal.

Describe the two main properties that define a heap and why they matter.

Think about the tree shape and how parent and child values relate.

Explain how a heap is stored in an array and how to find parent and child nodes using indices.

Remember the formulas for navigating a binary heap in an array.

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 tree is always a complete binary tree but unordered

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: Check other options

   Every parent node is less than or equal to its children describes a min-heap, C is not true for heaps, and D is partially true but incomplete without heap order.

3. Final Answer:

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

4. Quick Check:

   Max-heap = Parent ≥ Children [OK]

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

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking all leaf nodes have same value
• Ignoring heap order property

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

easy

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

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

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

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

Solution

1. Step 1: Recall array indexing for heap

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

2. Step 2: Verify options

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 matches zero-based indexing. Parent at index i, left child at 2*i, right child at 2*i + 1 is for one-based indexing. Options A and C are incorrect formulas.

3. Final Answer:

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

4. Quick Check:

   Zero-based heap indexing = 2*i+1, 2*i+2 [OK]

Hint: Zero-based heap uses 2*i+1 and 2*i+2 for children [OK]

Common Mistakes:

• Using one-based indexing formulas in zero-based arrays
• Mixing up left and right child formulas
• Using division instead of multiplication for child indices

3. Consider the following max-heap array representation: [40, 30, 35, 15, 10, 25]. What will be the array after inserting 50 and re-heapifying?

medium

A. [50, 30, 40, 15, 10, 25, 35]

B. [40, 30, 35, 15, 10, 25, 50]

C. [50, 40, 35, 15, 30, 25, 10]

D. [40, 35, 30, 15, 10, 25, 50]

Solution

1. Step 1: Insert 50 at the end

   Array becomes [40, 30, 35, 15, 10, 25, 50].

2. Step 2: Re-heapify by bubbling up 50

   Parent of index 6 is (6-1)//2=2 (35 < 50), swap 6 and 2: [40, 30, 50, 15, 10, 25, 35]. Now at 2, parent 0 (40 < 50), swap 2 and 0: [50, 30, 40, 15, 10, 25, 35]. Heap property restored.

3. Final Answer:

   [50, 30, 40, 15, 10, 25, 35] -> Option A

4. Quick Check:

   Insert 50, bubble up to root [OK]

Hint: Insert at end, bubble up until parent ≥ node [OK]

Common Mistakes:

• Not bubbling up after insertion
• Swapping with wrong parent index
• Leaving new element at the end without re-heapify

4. The following C code snippet is intended to heapify a subtree rooted at index i in a max-heap array arr of size n. What is the error?

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int 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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

medium

A. Swapping elements before checking if largest changed

B. Incorrect calculation of left and right child indices

C. Missing base case to stop recursion

D. No error; code correctly heapifies the subtree

Solution

1. Step 1: Analyze child index calculation

   Left and right child indices are correctly calculated as 2*i+1 and 2*i+2 for zero-based arrays.

2. Step 2: Check recursion and swapping logic

   Swapping happens only if largest changes, then recursive call heapifies the affected subtree. No base case needed explicitly as recursion stops when largest == i.

3. Final Answer:

   No error; code correctly heapifies the subtree -> Option D

4. Quick Check:

   Heapify logic correct and complete [OK]

Hint: Heapify swaps and recurses only if needed [OK]

Common Mistakes:

• Thinking explicit base case needed for recursion
• Miscomputing child indices
• Swapping unconditionally without checking largest

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25, 30]. You want to replace the root with 22 and restore the min-heap property. What will be the resulting array after heapifying?

hard

A. [10, 20, 15, 30, 25, 22]

B. [10, 20, 15, 22, 25, 30]

C. [15, 20, 22, 30, 25, 10]

D. [22, 10, 15, 20, 25, 30]

Solution

1. Step 1: Replace root with 22

   Array becomes [22, 10, 15, 20, 25, 30].

2. Step 2: Heapify down from root

   Compare 22 with children 10 and 15. 10 is smallest, swap 22 and 10: [10, 22, 15, 20, 25, 30]. Then heapify at index 1: compare 22 with children 20 and 25, 20 is smaller, swap: [10, 20, 15, 22, 25, 30]. No further swaps needed.

3. Final Answer:

   [10, 20, 15, 22, 25, 30] -> Option B

4. Quick Check:

   Replace root, bubble down to restore min-heap [OK]

Hint: Replace root, swap with smaller child until heap restored [OK]

Common Mistakes:

• Swapping with larger child instead of smaller
• Not continuing heapify after first swap
• Confusing min-heap with max-heap rules