Heap Sort

Definition

Heap Sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to Selection Sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

How it Works (Step-by-Step)

1. Build a Max Heap: First, organize the messy array into a valid Max Heap structure. This puts the largest item at the very start of the array.
2. Swap: Swap the first element (largest) with the last element. The largest item is now sorted at the end of the array.
3. Heapify: The remaining elements at the top are now disorganized. “Heapify” (re-organize) them so they form a Max Heap again.
4. Repeat: Repeat steps 2 and 3 until the entire array is sorted.

Example

Unsorted Array: [4, 10, 3, 5, 1]

1. Build Max Heap: [10, 5, 3, 4, 1]
2. Swap Root (10) with Last (1): [1, 5, 3, 4, 10] (10 is now sorted)
3. Heapify the rest: New Max Heap is [5, 4, 3, 1]
4. Swap Root (5) with Last (1): [1, 4, 3, 5, 10] (5 and 10 are sorted)
5. Repeat…

Code Example (Python)

Python

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    l = 2 * i + 1     # left = 2*i + 1
    r = 2 * i + 2     # right = 2*i + 2

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

    # See if right child of root exists and is greater than root
    if r < n and arr[r] > arr[largest]:
        largest = r

    # Change root, if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        # Heapify the root.
        heapify(arr, n, largest)

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

    # Build a maxheap.
    for i in range(n // 2 – 1, –1, –1):
        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)

arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print(“Sorted array is:”, arr)
# Output: [5, 6, 7, 11, 12, 13]

Complexity Analysis

• Time Complexity: O(n log n) for best, average, and worst cases. This makes it very consistent.

• Space Complexity: O(1). It sorts “in-place,” meaning it doesn’t need extra memory arrays like Merge Sort does.

Use Cases

• Embedded Systems: Because it uses fixed memory (O(1) space), it’s great for systems with very limited RAM (like sorting on a microcontroller).
  
• Safety-Critical Systems: Since its worst-case scenario is still O(n log n) (unlike QuickSort which can degrade to O(n^2)), it is used where predictable timing is mandatory.