Heap Sort

Idea

Heap Sort leverages a heap: build a max-heap (or min-heap), repeatedly take the top element to the end, adjust the remaining heap, and continue until sorted.

堆排序演示

105341

当前堆顶: 10

下一步

Algorithm

1. Build a max-heap from the array.
2. Swap heap top (max) with the last element; heap size minus 1.
3. Heapify the remaining elements.
4. Repeat steps 2–3 until one element remains.

Pseudo-code:

function heapSort(A, n):
    buildMaxHeap(A, n)
    for i = n-1 downto 1:
        swap(A[0], A[i])
        heapify(A, 0, i)

function buildMaxHeap(A, n):
    for i = n/2-1 downto 0:
        heapify(A, i, n)

function heapify(A, i, n):
    largest = i
    l = 2*i+1
    r = 2*i+2
    if l < n and A[l] > A[largest]:
        largest = l
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        swap(A[i], A[largest])
        heapify(A, largest, n)

Complexity

• Best/worst/avg: $O(n\log n)$
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

For $A = [4, 10, 3, 5, 1]$, show the initial heap and the state after the first swap.

参考答案

思路：先建大顶堆，再交换。

步骤：

1. 初始建堆：[10, 5, 3, 4, 1]
2. 第一次交换：[1, 5, 3, 4, 10]，调整为新堆：[5, 4, 3, 1, 10]

答案：如上，最大元素归位。

Exercise 2

What are heap sort’s time and space complexities?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n\log n)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n\log n)$，空间 $O(1)$。

PreviousQuick SortQuick sort fundamentals, algorithm flow, complexity, and practice. NextMerge SortMerge sort fundamentals, algorithm flow, complexity, and practice.