Heap Sort Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA C

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = [1];
}

Drag options to blanks, or click blank then click option'

Atemp

B*b

C*a

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning *a to *b instead of using temp

Using 0 instead of temp

Swapping values incorrectly causing data loss

The variable temp temporarily holds the value of *a so that *b can be assigned to *a without losing the original value. Then *b is assigned the value stored in temp.

2fill in blank

medium

Complete the code to heapify a subtree rooted with index i in array of size n.

DSA C

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[[1]])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

Drag options to blanks, or click blank then click option'

Alargest

Bleft

Cright

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing left child with right child instead of root

Using wrong index variable

Confusing largest with left or right

We compare the left child arr[left] with the root arr[i] to find the largest value.

3fill in blank

hard

Fix the error in the loop that builds the heap from the array.

DSA C

for (int i = n / 2 - 1; i >= [1]; i--) {
    heapify(arr, n, i);
}

Drag options to blanks, or click blank then click option'

A1

Bn/2

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 causes skipping the root

Using n or n/2 causes out of bounds or incomplete heapify

The loop must run from the last non-leaf node down to index 0 to build the max heap correctly.

4fill in blank

hard

Fill both blanks to complete the heap sort extraction loop.

DSA C

for (int i = n - 1; i > [1]; i--) {
    swap(&arr[0], &arr[[2]]);
    heapify(arr, i, 0);
}

Drag options to blanks, or click blank then click option'

A0

Bi

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop condition causing infinite loop

Swapping with wrong index causing incorrect sorting

The loop runs until i > 0 and swaps the root arr[0] with the last element arr[i] before heapifying the reduced heap.

5fill in blank

hard

Fill all three blanks to complete the heap sort function.

DSA C

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= [1]; i--) {
        heapify(arr, n, [2]);
    }
    for (int i = n - 1; i > [3]; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

Drag options to blanks, or click blank then click option'

A0

Bi

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop bounds causing incomplete heap

Passing wrong index to heapify

Incorrect loop condition in second loop

The first loop heapifies from last non-leaf node down to 0. The second loop extracts elements until i > 0.

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