Understanding Heap Sort: Theory, Implementation, and Key Insights

Heap sort is a comparison‑based sorting algorithm that leverages a binary heap (typically a max‑heap) to repeatedly extract the largest element and rebuild the heap until the entire array is sorted.

The article begins with a brief introduction to heaps, defining a max‑heap as a complete binary tree where each node’s value is greater than or equal to its children, and a min‑heap as the opposite.

It then explains the core idea of heap sort: first build a max‑heap from the input array, then repeatedly swap the root (the current maximum) with the last unsorted element and restore the heap property on the remaining elements.

Q&A : The author notes that the heap’s structure inherently “remembers” the ordering because each parent node dominates its children, which aids in understanding why the algorithm works.

Implementation (Java):

/**
 * 堆排序
 *
 * @param arr
 */
public void sort(int[] arr) {
    System.out.println("初始序列状态: " + Arrays.toString(arr) + "\n");
    int len = arr.length;
    // 构建初始大顶堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        System.out.println("构建初始大顶堆: " + i);
        heapAdjust(arr, i, len - 1);
    }
    // 交换堆顶元素和未排序序列的最后一个元素,并重新构建大顶堆
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i); // 元素交换
        heapAdjust(arr, 0, i - 1);
    }
}

/**
 * 将 arr[pos...off] 构建成大顶堆
 *
 * @param arr
 * @param pos
 * @param off
 */
public void heapAdjust(int[] arr, int pos, int off) {
    int j, temp = arr[pos];
    System.out.println("--此次循环的堆顶: " + temp);
    int init_j = pos * 2 + 1;
    for (j = init_j; j <= off; j = j * 2 + 1) {
        System.out.println("---循环索引值: " + j + " 数值: " + arr[j]);
        if (j < off && arr[j] < arr[j + 1]) {
            System.out.println("---左右子节点对比: 左 " + arr[j] + " 小于右 " + arr[j + 1]);
            ++j;
        }
        // 节点不小于左右孩子节点
        if (temp >= arr[j]) {
            System.out.println("---此次循环的堆顶: " + temp + " 大于左右子节点!");
            break;
        }
        int exchange = arr[j];
        arr[pos] = arr[j];
        pos = j;
        arr[pos] = temp;
        System.out.println("---交换位置: " + arr[pos] + " 和 " + exchange);
    }
    arr[pos] = temp;
    System.out.println("--当前序列状态: " + Arrays.toString(arr) + "\n");
}

The article also lists key points such as initializing the max‑heap, swapping the root with the last element, and rebuilding the heap after each extraction.

An example array int[] arr = {13, 14, 99, 33, 82, 25, 59, 94} is used to illustrate why the first heap‑building loop starts from index len/2‑1 (the last non‑leaf node) and proceeds upward.

Visual diagrams (omitted here) show the step‑by‑step transformation of the array into a heap and the subsequent sorting phases.

Conclusion : By mapping a linear array to a complete binary tree and exploiting the heap property, heap sort achieves O(n log n) time complexity with in‑place memory usage, demonstrating the power of algorithmic design.