Heap Sort Algorithm | Efficient Comparison-based Sorting Method

Description

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides its input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.

History

Heap Sort was invented by J.W.J. Williams in 1964, marking a significant milestone in the history of sorting algorithms. The algorithm was first published in the paper "Algorithm 232 - Heapsort" in the Communications of the ACM. The development of Heap Sort was particularly notable because it was the first sorting algorithm to achieve optimal time complexity O(n log n) in the worst case while using only O(1) auxiliary space. This was a significant improvement over Quick Sort's worst-case time complexity of O(n²). The binary heap data structure, which is fundamental to Heap Sort, was also introduced in this same paper. Robert W. Floyd later improved the algorithm in 1964 with his "bottom-up" heap construction method, which reduced the complexity of building the initial heap from O(n log n) to O(n).

Understanding Heaps

A binary heap is a complete binary tree with the following properties:

Structure Property: A binary heap is a complete binary tree, which means all levels are fully filled except possibly the last level, which is filled from left to right.
Heap Property: In a max-heap, for any given node I, the value of I is greater than or equal to the values of its children. The opposite is true for a min-heap.

For an array-based implementation, given an index i:

Parent(i) = ⌊(i - 1) / 2⌋

LeftChild(i) = 2i + 1

RightChild(i) = 2i + 2

How It Works

Build Max Heap: Convert the input array into a max heap structure
Heapify: Recursively ensure the heap property is maintained
Extract and Sort:
- Swap the root (maximum element) with the last element
- Reduce heap size by 1
- Heapify the root to maintain the heap property
- Repeat until heap is empty

Visualization

Speed:

Click Start to begin visualization

Implementation


class HeapSort:
    @staticmethod
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        # Compare with left child
        if left < n and arr[left] > arr[largest]:
            largest = left

        # Compare with right child
        if right < n and arr[right] > arr[largest]:
            largest = right

        # If largest is not root
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            HeapSort.heapify(arr, n, largest)

    @staticmethod
    def sort(arr):
        n = len(arr)

        # Build max heap
        for i in range(n // 2 - 1, -1, -1):
            HeapSort.heapify(arr, n, i)

        # Extract elements from heap one by one
        for i in range(n - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            HeapSort.heapify(arr, i, 0)

        return arr

# Example usage
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    HeapSort.sort(arr)
    print("Sorted array:", arr)


#include <iostream>
#include <vector>

class HeapSort {
private:
    static void heapify(std::vector<int>& arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

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

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

        if (largest != i) {
            std::swap(arr[i], arr[largest]);
            heapify(arr, n, largest);
        }
    }

public:
    static void sort(std::vector<int>& arr) {
        int n = arr.size();

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            std::swap(arr[0], arr[i]);
            heapify(arr, i, 0);
        }
    }
};

// Example usage
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    HeapSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}


public class HeapSort
{
    private static void Heapify(int[] arr, int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

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

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

        if (largest != i)
        {
            (arr[i], arr[largest]) = (arr[largest], arr[i]);
            Heapify(arr, n, largest);
        }
    }

    public static void Sort(int[] arr)
    {
        int n = arr.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);

        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--)
        {
            (arr[0], arr[i]) = (arr[i], arr[0]);
            Heapify(arr, i, 0);
        }
    }

    // Example usage
    public static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Complexity Analysis

Operation	Time Complexity
Build Heap	O(n)
Heapify	O(log n)
Overall Sorting	O(n log n)

Quick Info

Heap Sort