Heap Sort Algorithm

Generated on 2025-07-10 02:06:17 Algorithm Cheatsheet for Technical Interviews

---

Heap Sort Algorithm Cheatsheet

1. Quick Overview

• What is it? Heap Sort is a comparison-based sorting algorithm that leverages the Heap data structure (typically a binary heap) to efficiently sort elements. It’s an in-place algorithm (mostly) known for its guaranteed O(n log n) time complexity.

• When to use it?

  • When you need a guaranteed O(n log n) sorting algorithm.
  • When space efficiency is a concern as it’s mostly in-place.
  • When you need to sort a large dataset, but quicksort is not reliable due to worst-case O(n^2) time complexity.
  • Avoid if your data is almost sorted, as other algorithms (like insertion sort) are more efficient in such scenarios.

2. Time & Space Complexity

Metric	Complexity	Explanation
Time Complexity
Best Case	O(n log n)	Building the heap takes O(n) and extracting each element takes O(log n). Even in the best case, heapify takes O(n) time.
Average Case	O(n log n)	Heapify and extract operations dominate the runtime.
Worst Case	O(n log n)	Even in the worst case, heapify and extract operations guarantee O(n log n) time.
Space Complexity	O(1)	In-place sorting. However, if a separate heap is created, the space complexity would be O(n). The “in-place” version directly modifies the input array, treating it as the heap. Auxiliary space used is minimal (primarily for swapping elements).

3. Implementation

Python

def heapify(arr, n, i):
    """Heapify a subtree rooted at index i.

    Args:
        arr: The array to heapify.
        n: The size of the heap.
        i: The index of the root of the subtree.
    """
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # left = 2*i + 1
    right = 2 * i + 2  # right = 2*i + 2

    # See if left child exists and is greater than root
    if left < n and arr[i] < arr[left]:
        largest = left

    # See if right child exists and is greater than largest so far
    if right < n and arr[largest] < arr[right]:
        largest = right

    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        heapify(arr, n, largest)  # Recursively heapify the affected sub-tree


def heap_sort(arr):
    """Sorts an array using Heap Sort.

    Args:
        arr: The array to sort.
    """
    n = len(arr)

    # Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):  # Start from the last non-leaf node
        heapify(arr, n, i)

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

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is", arr) # Output: Sorted array is [5, 6, 7, 11, 12, 13]

Java

public class HeapSort {

    public static void heapify(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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

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

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

        // Build heap (rearrange array)
        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
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

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

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.print("Sorted array is: ");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " "); // Output: Sorted array is: 5 6 7 11 12 13
    }
}

C++

#include <iostream>
#include <vector>

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);
    }
}

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

    // Build heap (rearrange array)
    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);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
    std::cout << "Sorted array is: ";
    for (int i = 0; i < arr.size(); ++i)
        std::cout << arr[i] << " "; // Output: Sorted array is: 5 6 7 11 12 13
    std::cout << std::endl;
    return 0;
}

4. Common Patterns

• Priority Queues: Heap sort is based on the heap data structure, which is the foundation for priority queues. You can use a heap to maintain a sorted collection of elements where the highest (or lowest) priority element is always readily accessible.
• K-th Largest/Smallest Element: Heaps are efficient for finding the k-th largest or smallest element in an array. Build a min-heap of size k to find the k-th smallest or a max-heap to find the k-th largest.
• Variations: There are variations like bottom-up heap construction that can improve performance slightly.

5. Pro Tips

• Heapify Optimization: The heapify operation is crucial. Understanding how it works recursively is key to optimizing.
• In-Place vs. Separate Heap: The in-place version is generally preferred for space efficiency. Creating a separate heap takes O(n) space.
• Understanding Indexing: Remember that in a binary heap, the left child of a node at index i is at 2*i + 1 and the right child is at 2*i + 2.
• Max vs. Min Heap: For ascending order sorting, use a max heap. For descending order, use a min heap.

6. Practice Problems

1. Kth Largest Element in an Array (LeetCode 215): Find the kth largest element in an unsorted array.
2. Sort an Array (LeetCode 912): Sort an array using any sorting algorithm (good practice to implement Heap Sort).
3. Merge k Sorted Lists (LeetCode 23): Merge k sorted linked lists into one sorted linked list. (A heap can be used to efficiently track the smallest current element from each list.)

7. Templates

C++

#include <iostream>
#include <vector>
#include <algorithm> // for std::swap

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

    // 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 heap (rearrange array) from bottom up
    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);
    }
}

//Example Usage:
/*
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);

    std::cout << "Sorted array: ";
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}
*/

Python

def heapify(arr, n, i):
    """Heapify a subtree rooted at index 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 heap_sort(arr):
    """Sorts an array using Heap Sort."""
    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:
"""
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is", arr)  # Output: Sorted array is [5, 6, 7, 11, 12, 13]
"""

Java

public class HeapSortTemplate {

    // Function to heapify a subtree rooted at index i
    public 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    // Main function to perform Heap Sort
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // Build heap (rearrange array)
        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--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    //Example Usage:
    /*
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);

        System.out.print("Sorted array: ");
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
    */
}

This cheatsheet provides a comprehensive and practical guide to the Heap Sort algorithm. It covers the essential aspects, from basic concepts to implementation details and optimization techniques, making it a valuable resource for developers.