Heap Sort

Heap Sort is a comparison-based sorting algorithm that works by first converting the input array into a max-heap or a min-heap, depending on whether you want to sort in ascending or descending order. Here, I'll provide a detailed algorithm for Heap Sort.

Algorithm: Heap Sort

Build a Max-Heap: Build a max-heap from the input array. A max-heap is a binary tree where each parent node is greater than or equal to its child nodes. This step ensures that the largest element is at the root of the heap.

Swap Root with Last Element: Swap the root element (the largest) with the last element in the heap. This ensures that the largest element is in its correct sorted position at the end of the array.

Heapify: After the swap, the heap property may be violated. To restore it, perform a heapify operation on the reduced heap (excluding the last element). This will bring the next largest element to the root.

Repeat: Repeat steps 2 and 3 until the entire array is sorted. The heap size decreases with each iteration.

Example

Let's correctly build the max-heap for the array [4, 10, 3, 5, 1]

Step 1: Build a Max-Heap

Starting array: [4, 10, 3, 5, 1]

Convert the array into a max-heap. Start from the last non-leaf node and perform heapify for each element.

Heapify at index 2 (element 3):
[4, 10, 3, 5, 1] -> [4, 10, 3, 5, 1]

No changes needed at index 2 as 3 is already larger than its children.

Heapify at index 1 (element 10):
[4, 10, 3, 5, 1] -> [4, 10, 3, 5, 1]

No changes needed at index 1 as 10 is already larger than its children.

Heapify at index 0 (element 4):
[4, 10, 3, 5, 1] -> [10, 5, 3, 4, 1]

Swap 4 with 10 to satisfy the max-heap property.

The array after building the max-heap: [10, 5, 3, 4, 1]

Step 2: Swap Root with Last Element and Heapify

Now, we swap the root (the largest element) with the last element and perform heapify on the reduced heap.

Swap the root (10) with the last element (1):

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

Perform heapify on the reduced heap (excluding the last element):

Heapify at index 0 (element 1):
[1, 5, 3, 4, 10] -> [5, 1, 3, 4, 10]
Swap 1 with 5 to satisfy the max-heap property.

Step 3: Repeat Step 2 Until Sorted

Continue swapping the root with the last element and heapify until the entire array is sorted.

Swap root (5) with last element (4):

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

Heapify:

Heapify at index 0 (element 4):

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

No changes needed at index 0 as 4 is already larger than its children.

Swap root (4) with last element (3):

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

Heapify:

Heapify at index 0 (element 3):
[3, 1, 4, 5, 10] -> [3, 1, 4, 5, 10]

No changes needed at index 0 as 3 is already larger than its children.

Swap root (3) with last element (1):
Now, the array is sorted:

Sorted array: [1, 3, 4, 5, 10]

Pseudo Code

HeapSort(arr,n):

   // n is length of arr

    # Build a max-heap

    for i from n/2 - 1 down to 0:

        heapify(arr, n, i)

    # One by one extract elements from the heap

    for i from n - 1 down to 1:

        # Swap the root (maximum element) with the last element

        swap(arr[0], arr[i])

        

        # Call heapify on the reduced heap

        heapify(arr, i, 0)

In the pseudo-code above, heapify is a function that ensures that the subtree rooted at a given index is a max-heap. It takes the array, the size of the heap, and the index as parameters and makes necessary swaps to maintain the max-heap property. The swap function is used to swap two elements in the array.

Time Complexity:

Build Max-Heap: Building the max-heap takes O(n) time, where n is the number of elements in the array. This is because we start from the middle of the array (the last non-leaf node) and perform heapify operations, which have a time complexity of O(log n), for each element.

Extract Max n times: After building the max-heap, we extract the maximum element (the root) and perform heapify on the remaining heap n times. Each heapify operation takes O(log n) time. Therefore, the total time complexity for extracting the max n times is O(n * log n).

The dominant factor in the time complexity is the O(n * log n) part, so the overall time complexity of Heap Sort is O(n * log n) for the worst, average, and best cases.

Space Complexity:

Heap Sort is an in-place sorting algorithm, which means it doesn't require additional memory for sorting. It sorts the array in place, so the space complexity is constant. The space complexity of Heap Sort is O(1).

In summary, Heap Sort has a time complexity of O(n * log n) and a space complexity of O(1). It is efficient for sorting large datasets and is particularly useful when a stable sort is not required, and you want to save memory by avoiding additional data structures.

C Program - Heap Sort

/*******************************************************************************/

#include <stdio.h>

// Function to perform heapify on a subtree rooted at index i in the given array

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

    int largest = i;    // Initialize largest as the root

    int left_child = 2 * i + 1;

    int right_child = 2 * i + 2;

    // Compare with left child

    if (left_child < n && arr[left_child] > arr[largest]) {

        largest = left_child;

    }

    // Compare with right child

    if (right_child < n && arr[right_child] > arr[largest]) {

        largest = right_child;

    }

    // If the largest is not the root, swap and continue heapifying

    if (largest != i) {

        int temp = arr[i];

        arr[i] = arr[largest];

        arr[largest] = temp;

        heapify(arr, n, largest);

    }

}

// Main function to perform Heap Sort

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

    // Build a max-heap

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

        heapify(arr, n, i);

    }

    // Extract elements from the heap one by one

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

        // Swap the root (maximum element) with the last element

        int temp = arr[0];

        arr[0] = arr[i];

        arr[i] = temp;

        // Call heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

int main() {

  int arr[50],n,i;

 

  printf("Enter size of the array: ");

  scanf("%d",&n);

  printf("Enter %d elements:\n",n);

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

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

    heapSort(arr, n);

    printf("\nSorted array: ");

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

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

        }

    return 0;

}