Heap Sort

Why did the heap sort algorithm join the circus? Because it was a master at juggling elements and keeping them in the right order under the big top!

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that efficiently sorts an array or list of elements by utilizing the properties of a binary heap data structure. It is known for its stability, relative simplicity, and consistent time complexity, making it suitable for a wide range of applications.

How it Works

Here's a step-by-step explanation of how Heap Sort works:

1. Heap Construction: The first step is to build a binary heap from the array. A binary heap is a complete binary tree where the value of each node is greater (in a max-heap) or smaller (in a min-heap) than or equal to the values of its children. Building the heap typically involves two main operations: heapify (adjusting the heap structure) and sift-down (correcting the violation of heap properties).

2. Sorting: Once the binary heap is constructed, the largest (in a max-heap) or smallest (in a min-heap) element is removed from the root and placed at the end of the array. This process is repeated until the entire array is sorted.

3. Heap Reorganization: After each removal of an element, the heap's structure may be violated. To maintain the heap properties, the heap is reorganized by moving the last element to the root and "sifting down" the new root element to its correct position in the heap.

4. Repeat: Steps 2 and 3 are repeated until all elements are removed from the heap and placed in their correct positions in the sorted array.

Heap Sort Code in Java:

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        heapSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void heapSort(int arr[]) {
        int n = arr.length;

        // 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--) {
            // Move the current root to the end of the array
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int arr[], int n, int root) {
        int largest = root;
        int leftChild = 2 * root + 1;
        int rightChild = 2 * root + 2;

        // Find the largest element among the root and its children
        if (leftChild < n && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < n && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // If the largest element is not the root, swap them and heapify the affected subtree
        if (largest != root) {
            int temp = arr[root];
            arr[root] = arr[largest];
            arr[largest] = temp;

            // Recursively heapify the affected subtree
            heapify(arr, n, largest);
        }
    }
}

Heap Sort Code in C:

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void heapify(int arr[], int n, int root) {
    int largest = root;
    int leftChild = 2 * root + 1;
    int rightChild = 2 * root + 2;

    // Find the largest element among the root and its children
    if (leftChild < n && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }
    if (rightChild < n && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If the largest element is not the root, swap them and heapify the affected subtree
    if (largest != root) {
        swap(&arr[root], &arr[largest]);

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

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--) {
        // Move the current root to the end of the array
        swap(&arr[0], &arr[i]);

        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {64, 34, 25, 

12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time and Space Complexity Analysis

The time complexity of Heap Sort can be analyzed mathematically as follows:

Let n be the number of elements in the array to be sorted.

Heap Sort follows the following steps:

1. Heap Construction: Building a binary heap from an unsorted array takes O(n) time. This step involves repeated heapify operations on each level of the heap, and there are log₂(n) levels, so the total time spent here is O(n).

2. Sorting: Repeatedly extracting the maximum (in a max-heap) or minimum (in a min-heap) element from the heap and performing a heapify operation takes O(log n) time per element. Since there are n elements to extract and heapify, this step takes O(n log n) time.

Combining these two steps, the total time complexity of Heap Sort is:

$(T(n) = O(n) + O(n \log n) = O(n \log n))$

This means that Heap Sort has a consistent time complexity of O(n log n), making it efficient for sorting large datasets. Unlike Quick Sort, Heap Sort does not exhibit a worst-case time complexity of O(n^2) and is well-suited for a variety of sorting scenarios.

So,

1. Time Complexity:

   1. Worst-case: O(n log n)

   2. Average-case: O(n log n)

   3. Best-case: O(n log n)

2. Space Complexity: O(1) (in-place sorting, no additional memory required)

Heap Sort consistently achieves a time complexity of O(n log n), making it efficient for sorting large datasets. It has good cache performance due to its memory access patterns. Additionally, it is stable and can be implemented as an in-place sorting algorithm, which means it doesn't require additional memory for sorting.