Heap Sort Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Heap Sort algorithm?

Heap Sort uses a special tree structure called a heap to sort elements. It builds a max heap to find the largest element quickly, then swaps it to the end and rebuilds the heap until sorted.

beginner

What is a max heap?

A max heap is a binary tree where each parent node is greater than or equal to its children. This property helps quickly find the largest element at the root.

intermediate

Why do we rebuild the heap after swapping the root with the last element in Heap Sort?

After swapping, the heap property might break. Rebuilding (heapify) fixes the heap so the largest element moves to the root again for the next swap.

intermediate

What is the time complexity of Heap Sort and why?

Heap Sort runs in O(n log n) time because building the heap takes O(n), and each of the n removals of the root requires O(log n) to restore the heap.

beginner

What is the space complexity of Heap Sort?

Heap Sort uses O(1) extra space because it sorts the array in place without needing extra arrays.

What data structure does Heap Sort use to organize elements?

A Heap

B Linked List

C Queue

D Stack

Heap Sort uses a heap, specifically a max heap, to organize elements for sorting.

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

A In the middle

B At the leaf nodes

C At the root

D At the last index

The largest element in a max heap is always at the root node.

What operation is performed after swapping the root with the last element in Heap Sort?

A Traversal

B Heapify

C Deletion

D Insertion

Heapify restores the heap property after the root is swapped with the last element.

What is the worst-case time complexity of Heap Sort?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Heap Sort always runs in O(n log n) time, even in the worst case.

Does Heap Sort require extra space proportional to input size?

A Yes, it needs O(n) extra space

B Yes, it needs O(n^2) extra space

C Yes, it needs O(log n) extra space

D No, it sorts in place

Heap Sort sorts the array in place using O(1) extra space.

Explain how Heap Sort uses a max heap to sort an array step-by-step.

Think about how the largest element moves to the end each time.

Describe the difference between building a heap and heapifying in Heap Sort.

One is initial setup, the other is repeated maintenance.

Practice

1. What is the main purpose of the heapify process in the Heap Sort Algorithm?

easy

A. To build a max heap or min heap from an unsorted array

B. To swap the first and last elements of the array

C. To reverse the array elements

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy heap property (max or min heap).

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting.

3. Final Answer:

   To build a max heap or min heap from an unsorted array -> Option A

4. Quick Check:

   Heapify builds heap = To build a max heap or min heap from an unsorted array [OK]

Hint: Heapify creates heap structure from array [OK]

Common Mistakes:

• Confusing heapify with swapping elements
• Thinking heapify reverses the array
• Assuming heapify counts elements

2. Which of the following is the correct way to swap two elements arr[i] and arr[j] in C during heap sort?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr[i], arr[j] = arr[j], arr[i];

Solution

1. Step 1: Recall C swap syntax

   In C, swapping requires a temporary variable to hold one value.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses temp variable correctly; others are invalid in C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C = temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Trying Python-style swap syntax in C
• Assigning without temp causing overwrite
• Using undefined swap function

3. What will be the output array after applying heap sort on arr = [4, 10, 3, 5, 1]?

medium

A. [1, 4, 3, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 3, 4, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Build max heap from array

   Max heap of [4,10,3,5,1] rearranges to [10,5,3,4,1].

2. Step 2: Extract max and sort

   Repeatedly swap max with last element and heapify to get sorted array [1,3,4,5,10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option C

4. Quick Check:

   Heap sort output = sorted array ascending = [1, 3, 4, 5, 10] [OK]

Hint: Heap sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Forgetting to heapify after swaps
• Assuming heap sort outputs descending order

4. Identify the error in this heap sort snippet in C:

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2*i;
  int right = 2*i + 1;
  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. The recursive call to heapify is missing

B. The swap logic is incorrect

C. The base case for recursion is missing

D. Left and right child indices should be 2*i + 1 and 2*i + 2

Solution

1. Step 1: Check child index calculation

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

2. Step 2: Verify other parts

   Swap and recursion are correct; base case is implicit by condition checks.

3. Final Answer:

   Left and right child indices should be 2*i + 1 and 2*i + 2 -> Option D

4. Quick Check:

   Child indices in 0-based heap = 2*i+1, 2*i+2 [OK]

Hint: Remember 0-based heap child indices [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Ignoring recursive heapify call
• Misplacing swap logic

5. Given an array with many duplicate elements, how does heap sort behave compared to quicksort in terms of stability and performance?

hard

A. Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²)

B. Heap sort is stable and faster than quicksort always

C. Heap sort is stable but slower than quicksort in all cases

D. Heap sort and quicksort are both stable and have same worst-case time

Solution

1. Step 1: Understand stability of heap sort

   Heap sort is not stable because it swaps elements without preserving order of equal keys.

2. Step 2: Compare performance with quicksort

   Heap sort guarantees O(n log n) time always; quicksort is faster on average but can degrade to O(n²).

3. Final Answer:

   Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²) -> Option A

4. Quick Check:

   Heap sort stable? No; Time? O(n log n) always [OK]

Hint: Heap sort stable? No; quicksort worst-case O(n²) [OK]

Common Mistakes:

• Assuming heap sort is stable
• Thinking quicksort worst-case is always O(n log n)
• Confusing stability with speed