Heap Sort Algorithm in DSA C - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.Imagine you have a messy pile of books and you want to arrange them from smallest to largest by height. Heap sort helps you organize the pile step-by-step so you can pick the smallest book easily each time.

🎯 Goal: Build a C program that sorts an array of integers using the heap sort algorithm. You will create the array, set up helper variables, write the heapify function to maintain the heap property, and then perform the sorting. Finally, you will print the sorted array.

📋 What You'll Learn

Create an integer array with exact values

Define the size of the array as a variable

Implement the heapify function to maintain max heap property

Implement the heap sort function using heapify

Print the sorted array after sorting

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in technical interviews and improves your grasp of efficient sorting algorithms used in software development.

1

Create the array of integers

Create an integer array called arr with these exact values: 12, 11, 13, 5, 6, 7.

DSA C

# Create the integer array arr with values 12, 11, 13, 5, 6, 7
// Your code here

Hint

Use the syntax int arr[] = {values}; to create the array.

2

Define the size of the array

Create an integer variable called n and set it to the size of the array arr (which is 6).

DSA C

int arr[] = {12, 11, 13, 5, 6, 7};
// Define the integer variable n as 6
// Your code here

Hint

Use int n = 6; to store the size of the array.

3

Implement the heapify function

Write a function called heapify that takes an integer array arr, an integer n for size, and an integer i for the index. This function should maintain the max heap property by comparing the parent node at i with its children and swapping if needed.

DSA C

int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;

// Write the heapify function below
// Your code here

Hint

Remember to check left and right children indices and swap if the child is larger than the parent.

4

Implement heap sort and print the sorted array

Write a function called heapSort that sorts the array arr of size n using the heapify function. Then, print the sorted array elements separated by spaces.

DSA C

int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  arr[largest])
        largest = left;

    if (right  arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

// Write the heapSort function and print the sorted array below
// Your code here

Hint

Build the max heap first, then swap the root with the last element and reduce heap size. Repeat until sorted.

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