📚 Heap Sort

• Heap Sort is a comparison-based sorting technique based on a special tree structure called a Heap.

• A Heap is a complete binary tree that satisfies the heap property.

• In a Max Heap, for every node i, the value of i is greater than or equal to the values of its children.

👉 In Heap Sort:

1. We build a Max Heap from the input data.

2. The largest item is stored at the root of the heap.

3. Replace it with the last item of the heap and reduce the heap size by 1.

4. Heapify the root again to maintain the Max Heap property.

5. Repeat this until the heap size is 1.

---

🛠️ Algorithm for Heap Sort

1. Build Max Heap from input array.

2. Repeat until heap size > 1:

   • Swap the root (maximum element) with the last element.

   • Reduce heap size by 1.

   • Heapify the root to restore heap property.

---

🔥 Heapify Algorithm (Maintain Max Heap property)

HEAPIFY(arr, n, i)
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]
        largest = left

    if right < n and arr[right] > arr[largest]
        largest = right

    if largest != i
        swap arr[i] and arr[largest]
        HEAPIFY(arr, n, largest)

---

📈 Example:

Input Array:
[4, 10, 3, 5, 1]

Step 1: Build a Max Heap

Max Heap:
[10, 5, 3, 4, 1]

Step 2: Sort

• Swap 10 and 1 → [1, 5, 3, 4, 10]

• Heapify → [5, 4, 3, 1, 10]

• Swap 5 and 1 → [1, 4, 3, 5, 10]

• Heapify → [4, 1, 3, 5, 10]

• Swap 4 and 3 → [3, 1, 4, 5, 10]

• Heapify → [3, 1, 4, 5, 10]

• Swap 3 and 1 → [1, 3, 4, 5, 10]

• Now sorted!

Final Sorted Array:
[1, 3, 4, 5, 10]

📌 Important points:

Feature	Details
Time Complexity	O(n log n) in all cases
Space Complexity	O(1) (in-place)
Stable?	❌ No, Heap Sort is not stable
Best for?	Large datasets when memory usage is critical

C Program - Heap Sort

#include <stdio.h>

// To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i) {

    int largest = i;       // Initialize largest as root

    int left = 2 * i + 1;   // left child

    int right = 2 * i + 2;  // right child

    // If left child is larger than root

    if (left < n && arr[left] > arr[largest])

        largest = left;

    // If right child is larger than largest so far

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

        largest = right;

    // If largest is not root

    if (largest != i) {

        int temp = arr[i];

        arr[i] = arr[largest];

        arr[largest] = temp;

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}

// Main function to do heap sort

void heapSort(int arr[], int n) {

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

    // One by one extract elements from heap

    for (int i = n - 1; i >= 0; i--) {

        // Move current root to end

        int temp = arr[0];

        arr[0] = arr[i];

        arr[i] = temp;

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

void printArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

void readArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        scanf("%d", &arr[i]);

    

}

int main() {

    int arr[50] ;

    int n;

    

    printf("Enter the number of elements \n");

    scanf("%d",&n);

    printf("Enter the array elements\n");

    readArray(arr,n);

    

    printf("Original array: ");

    printArray(arr, n);

    heapSort(arr,n);

    printf("Sorted array: ");

    printArray(arr, n);

    return 0;

}

Output

Enter the number of elements 

6

Enter the array elements

7 4 9 5 6 1 

Original array: 7 4 9 5 6 1 

Sorted array: 1 4 5 6 7 9