Heapsort

Heapsort is an efficient, in-place sorting algorithm that leverages the structure of a binary heap. In this tutorial, we'll break down the concepts behind heapsort step by step, so you gain a clear understanding of how it works and how to implement it.

Definition

Heapsort is a comparison-based sorting method that uses a binary heap—a complete binary tree where each parent node is larger (in a max heap) than its children. When implemented on arrays, this data structure lets us quickly locate the largest (or smallest) element and systematically organize the array into sorted order.

Process

The core idea of heapsort is similar to selection sort, but the selection is based on the heap structure. The algorithm performs the following steps:

Building the Heap

1. Construct a Max Heap:
   Rearrange the array into a max heap. In a max heap, the largest element is always at the root. Working from the last non-leaf node up to the root, we adjust each node to ensure the heap property is maintained.

2. Understanding the Array Representation:
   When modeling a binary heap on an array, if a node is located at index $i$, its relationships are as follows:

   $$Parent(i) = \left\lfloor\frac{i-1}{2}\right\rfloor$$ $$LeftChild(i) = 2 \times i + 1$$ $$RightChild(i) = 2 \times i + 2$$

Sorting the Array

Once the max heap is established, the sorting proceeds with these steps:

1. Extract the Maximum:
   The element at the root (the maximum) is swapped with the last element of the heap (the current unsorted portion of the array). This places the largest element in its correct final position.

2. Restore the Heap:
   After swapping, the heap property might be violated. Perform a "sift-down" operation on the new root to restore the max heap structure for the remaining unsorted elements.

3. Repeat:
   Repeat the above two steps. In each iteration, the heap size shrinks as one more element is sorted. After repeating the process $n - 1$ times (for an array of $n$ elements), the array becomes fully sorted.

Properties

Stability

Like selection sort, heapsort is not a stable sorting algorithm. The swapping of elements during the sift-down operations means that equal elements might not retain their original order.

Time Complexity

Heapsort runs in $O(n \log n)$ time in the best, average, and worst scenarios. This consistency makes heapsort a reliable choice in terms of performance.

Space Complexity

Since heapsort organizes the array in place without needing additional storage, it is considered an in-place algorithm with a space complexity of $O(1)$.

Implementation

Below is a Python implementation of heapsort designed with clarity in mind:

def sift_down(arr, start, end):
    """
    Adjusts the heap by sifting down the element at index `start`
    until the subtree rooted at `start` satisfies the max heap property.
    """
    parent = start
    child = 2 * parent + 1  # Left child index
    while child <= end:
        # Select the larger child
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        # If the parent is larger than the largest child, the heap is valid
        if arr[parent] >= arr[child]:
            return
        # Otherwise, swap and continue sifting down
        arr[parent], arr[child] = arr[child], arr[parent]
        parent = child
        child = 2 * parent + 1
 
def heap_sort(arr):
    """
    Sorts the input list `arr` in ascending order using the heapsort algorithm.
    """
    n = len(arr)
    # Build the max heap from the array.
    for i in range((n - 2) // 2, -1, -1):
        sift_down(arr, i, n - 1)
    
    # Extract elements one by one from the heap.
    for i in range(n - 1, 0, -1):
        # Move the current largest element to its correct position.
        arr[0], arr[i] = arr[i], arr[0]
        # Restore the max heap property for the reduced heap.
        sift_down(arr, 0, i - 1)

In this implementation:

• The sift_down function ensures the subtree rooted at a given index maintains the max heap property.
• The heap_sort function first builds the max heap from the array, then repeatedly swaps the root with the last unsorted element and readjusts the heap.

By following these steps, heapsort efficiently sorts the array in-place with a reliable time complexity of $O(n \log n)$.

This explanation and code illustrate how heapsort organizes, sorts, and gradually shrinks the unsorted portion of the array until the entire array is sorted. Feel free to experiment with this code to better understand the mechanics of heapsort!