Heap Sort Visualization

Watch the binary heap construction and adjustment process

Heap Sort is a sorting algorithm that uses the heap data structure. It first builds a max-heap from the array (where parent nodes are always larger than children), then repeatedly extracts the maximum element from the top, places it at the end of the array, and adjusts the remaining elements to reform the heap, until all elements are extracted.

Array View
Click 'Start Sorting' to view animation

Algorithm Steps

  1. Build a max-heap from the array (Build Max-Heap)
  2. The root element (arr[0]) is now the maximum
  3. Swap root with the last element
  4. Reduce heap size by 1, heapify the new root
  5. Repeat steps 3-4 until heap size is 1

Time and Space Complexity

Case Time Complexity Description
Build Heap O(n) Bottom-up heap construction complexity
Sort (All Cases) O(n log n) O(log n) adjustment per extraction
Space Complexity O(1) In-place sorting, only constant extra space

堆排序是不Stable Sort，相等元素的相对顺序可能改变。

Use Cases

  • Need in-place sorting with guaranteed O(n log n) worst case
  • Implementing priority queue data structures
  • Finding top K largest/smallest elements
  • System scheduling and task priority management
Priority Queue Top-K Problem Task Scheduling Memory-Constrained

Implementation

def heapify(arr, n, i):
    """维护最大堆性质"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 左子节点更大
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 右子节点更大
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 如果最大值不是根节点，交换并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    """堆排序算法"""
    n = len(arr)
    
    # 构建最大堆（从最后一个非叶节点开始）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个取出堆顶元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 交换堆顶和末尾
        heapify(arr, i, 0)  # 重新调整堆
    
    return arr


# 使用示例
arr = [12, 11, 13, 5, 6, 7]
print(heap_sort(arr))
# 输出: [5, 6, 7, 11, 12, 13]
public class HeapSort {
    
    /**
     * 维护最大堆性质
     */
    private 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 temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            
            heapify(arr, n, largest);
        }
    }
    
    /**
     * 堆排序算法
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 逐个取出堆顶元素
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            heapify(arr, i, 0);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        // 输出: [5, 6, 7, 11, 12, 13]
    }
}