Heap Sort Algorithm

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that utilizes a binary heap data structure. It is an in-place, non-recursive, and efficient sorting algorithm with a time complexity of O(n log n). Heap Sort is based on the concept of creating a binary heap (either max-heap or min-heap) from the input data and then repeatedly extracting the largest (or smallest) element from the heap and placing it at the end of the array.

Heap Sort is considered an improvement over selection sort because, instead of scanning the array to find the maximum element, it uses a heap to efficiently get the maximum element in O(log n) time.

How Heap Sort Works

Heap Sort works by first building a max-heap from the input array. Once the max-heap is built, the largest element (the root of the heap) is swapped with the last element of the array, reducing the size of the heap by one. The heap is then re-heapified (restoring the heap property), and this process is repeated until the entire array is sorted.

Step-by-step explanation:

  1. Build a Max-Heap: Convert the input array into a max-heap. In a max-heap, each parent node is greater than or equal to its children.
  2. Swap the Root with the Last Element: Swap the root (largest element) with the last element of the heap.
  3. Reduce the Heap Size: Decrease the size of the heap by one (ignore the last element, as it is already sorted).
  4. Heapify the Root: Restore the max-heap property by heapifying the root element.
  5. Repeat the process until all elements are sorted.

Example of Heap Sort

Let’s take an example of sorting the array [12, 11, 13, 5, 6, 7]:

  1. Initial List: [12, 11, 13, 5, 6, 7]
  2. Build a Max-Heap:
    • Max-heap: [13, 11, 12, 5, 6, 7]
  3. First Step (Extract Max):
    • Swap the root (13) with the last element (7): [7, 11, 12, 5, 6, 13]
    • Reduce the heap size and heapify the root: [12, 11, 7, 5, 6, 13]
  4. Second Step (Extract Max):
    • Swap the root (12) with the second-last element (6): [6, 11, 7, 5, 12, 13]
    • Heapify the root: [11, 6, 7, 5, 12, 13]
  5. Repeat the process until the array is sorted: [5, 6, 7, 11, 12, 13]

C++ Program to implement Heap Sort Algorithm

cpp
#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at node i
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) {
        swap(arr[i], arr[largest]);  // Swap root and the largest child

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

// Function to perform heap sort
void heapSort(int arr[], int n) {
    // Build the 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 (largest element) to the end
        swap(arr[0], arr[i]);

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

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Java Program to implement Heap Sort Algorithm

java
public class Main {
    // Function to heapify a subtree rooted at node i
    public static 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 swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

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

    // Function to perform heap sort
    public static void heapSort(int arr[]) {
        int n = arr.length;

        // Build the 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 (largest element) to the end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

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

    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main function
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Original array:");
        printArray(arr);

        heapSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Python Program to implement Heap Sort Algorithm

python
# Function to heapify a subtree rooted at node i
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # If right child is larger than largest so far
    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]  # Swap

        # Recursively heapify the affected subtree
        heapify(arr, n, largest)

# Function to perform heap sort
def heap_sort(arr):
    n = len(arr)

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

    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        # Move the current root (largest element) to the end
        arr[i], arr[0] = arr[0], arr[i]

        # Heapify the reduced heap
        heapify(arr, i, 0)

# Function to print the array
def print_array(arr):
    print(" ".join(map(str, arr)))

# Main function
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]

    print("Original array:")
    print_array(arr)

    heap_sort(arr)

    print("Sorted array:")
    print_array(arr)

Properties of Heap Sort

  • Time Complexity:
    • Best Case: O(n log n)
    • Average Case: O(n log n)
    • Worst Case: O(n log n)
  • Space Complexity: O(1) - Heap Sort is an in-place sorting algorithm, meaning it doesn't require extra space beyond the input array.
  • Stability: Heap Sort is not a stable sorting algorithm, meaning it may change the relative order of equal elements.
  • Adaptability: Heap Sort is not adaptive. It always has a time complexity of O(n log n), regardless of whether the input is already sorted.

When to Use Heap Sort

Heap Sort is often used when stability is not required, and memory usage needs to be minimized. Since it has a consistent O(n log n) time complexity in the worst, average, and best cases, it is a reliable choice for large datasets. However, because of its lack of stability, other algorithms like Merge Sort or Quick Sort might be preferred when stability is necessary.

DSA

5372

279

Related Articles