Detailed Explanation of Heap Sort in C Language

Heap Sort is an efficient sorting algorithm based on the heap data structure. It utilizes the properties of heaps (where the value of the parent node is greater than or equal to or less than or equal to the values of its child nodes) to achieve sorting. Heap Sort is also based on the idea of selection sort but optimizes the process of finding the extreme value through the heap structure.Below is a detailed analysis of the method for implementing heap sort in C language:

Basic Principles of Heap Sort

Heap Sort mainly consists of two stages:

1. Building the HeapConvert the unordered array into a max heap (or min heap). A max heap means that the value of each parent node is greater than or equal to the values of its left and right child nodes.
2. Sorting PhaseRepeatedly swap the top element of the heap (the maximum value) with the last element of the heap, then readjust the remaining elements into a max heap until the entire array is sorted.

Code Implementation<span><span>Main function for heap sort</span></span>

// Main function for heap sort
void heapSort(int arr[], int n) {
    // 1. Build a max heap (adjust from the last non-leaf node upwards)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // 2. Gradually extract the top element (maximum value) and adjust the heap
    for (int i = n - 1; i > 0; i--) {
        // Swap the current top of the heap (maximum value) with the last element
        swap(&arr[0], &arr[i]);
        // Readjust the remaining elements into a max heap (reduce heap size by 1)
        heapify(arr, i, 0);
    }
}

• Function: Implements the complete process of heap sort

• Implementation Steps:
• Swap the top element of the heap (maximum value) with the last element of the current heap
• Reduce the heap size by 1 (excluding the sorted elements)
• Call<span>heapify</span> on the new root node, to maintain the heap property
• Repeat the above steps until all elements are sorted

1. Building the Max HeapStart from the last non-leaf node (index<span>n/2-1</span>) and call<span>heapify</span> upwards to adjust each subtree

Heap Adjustment Function: Adjusts the subtree rooted at root into a max heap

// Heap adjustment function: Adjusts the subtree rooted at root into a max heap
// n: size of the heap
void heapify(int arr[], int n, int root) {
    int largest = root;       // Initialize largest as root
    int left = 2 * root + 1;  // Left child index = 2*root + 1
    int right = 2 * root + 2; // Right child index = 2*root + 2

    // If left child is greater than root
    if (left < n && arr[left] > arr[largest])
        largest = left;
    // If right child is greater than current largest
    if (right < n && arr[right] > arr[largest])
        largest = right;
    // If largest is not root, swap and recursively adjust
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        // Recursively adjust affected subtree
        heapify(arr, n, largest);
    }
}

• Function: Adjusts the subtree rooted at<span>root</span> into a max heap
• Implementation Steps:

1. Compare the root node with the left and right child nodes to find the maximum value
2. If the maximum value is not the root node, swap the root node with the maximum value node
3. Recursively adjust the affected subtree

Main Function

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);
    heapSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

Auxiliary Functions

// Print array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Swap the values of two integers
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

Characteristics of Heap Sort

• Advantages
• Stable time complexity: Best, worst, and average cases areO(n log n)
• In-place sorting: Requires only O(1) additional space (excluding the recursive stack)
• Suitable for handling large-scale data
• Disadvantages
• Unstable sorting algorithm (the relative position of equal elements may change)
• Poor cache friendliness (large jumps in accessing elements)
• Recursive implementation may incur stack space overhead

Applicable Scenarios

• Sorting scenarios that require stable time complexity of O(n log n)
• Memory-constrained scenarios that require in-place sorting
• Scenarios where sorting stability is not a concern