Heap sort hoạt động như thế nào?

Question

Accepted Answer

**Heap sort** xây dựng một **binary heap** từ mảng, rồi liên tục trích xuất giá trị lớn nhất để tạo ra thứ tự đã sắp xếp. Nó chạy trong **O(n log n)** và **tại chỗ** (in-place).

## Ý tưởng

Một max-heap giữ phần tử lớn nhất ở gốc. Xây dựng heap (O(n)), rồi hoán đổi gốc xuống cuối, thu nhỏ heap, và tái lập heap (sift down) — n lần.

## Ví dụ

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap trong O(n)
    return [heapq.heappop(arr)       # lấy ra phần tử nhỏ nhất n lần
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Một cài đặt kinh điển thực hiện tại chỗ bằng cách sift down ngay trong mảng.

## Độ phức tạp

- **Thời gian:** O(n log n) trong mọi trường hợp. **Bộ nhớ:** O(1) tại chỗ.

## Khi nào dùng / những cạm bẫy

Dùng khi bạn cần **O(n log n) được đảm bảo** *và* **bộ nhớ phụ O(1)** (merge sort cần O(n); quicksort có nguy cơ O(n²)). Nó **không ổn định** và có tính cục bộ cache kém, nên trong thực tế thường chậm hơn quicksort. Cùng một heap đó vận hành cho **priority queue** (hàng đợi ưu tiên) và tìm top-k phần tử.

## Tại sao điều này quan trọng

Heap sort là thuật toán sắp xếp phổ biến duy nhất vừa có trường hợp xấu nhất O(n log n) vừa tại chỗ, khiến nó có giá trị trong các bối cảnh hạn chế bộ nhớ hoặc cần giới hạn đảm bảo.

Cấu trúc heap bên dưới hữu ích rộng rãi — priority queue, thuật toán Dijkstra, và top-k streaming.

Nó củng cố ý tưởng rằng cấu trúc dữ liệu đúng làm cho một thuật toán hiệu quả.