Heap Sort

Concept

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max-heap from the input array, and then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted array.

Characteristics

• Time Complexity:
  • Worst-case: O(n log n)
  • Average-case: O(n log n)
  • Best-case: O(n log n)
• Space Complexity: O(1) (in-place sorting)
• Stability: Not stable
• Efficient for medium-sized datasets.

Code Example (C++)

#include <iostream>
#include <vector>
#include <algorithm>

// Function to heapify a subtree rooted at node i
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left = 2*i + 1
    int right = 2 * i + 2; // right = 2*i + 2

    // 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) {
        std::swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Main function to perform heap sort
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

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

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        std::swap(arr[0], arr[i]);

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

// Helper function to print the vector
void printVector(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    std::cout << "Unsorted array: ";
    printVector(data);

    heapSort(data);

    std::cout << "Sorted array: ";
    printVector(data);

    return 0;
}
// To compile and run (e.g., with g++):
// g++ your_file_name.cpp -o heap_sort_cpp
// ./heap_sort_cpp

Code Example (Python)

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

    if left < n and arr[i] < arr[left]:
        largest = left

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

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

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

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

# Example usage:
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7]
    print("Unsorted array:", data)

    heapSort(data)

    print("Sorted array:", data)

# To run:
# python your_file_name.py