Sắp xếp · Heap · Cây nhị phân

Heap Sort

Xây dựng Max-Heap từ mảng, sau đó liên tục lấy phần tử lớn nhất ra và đặt về cuối. Đảm bảo O(n log n) trong mọi trường hợp.

● Medium Mọi trường hợp: O(n log n)Space: O(1)Unstable ✗

Tốc độ

Heap chưa xử lý Đang heapify (root) Đang so sánh Hoán đổi Đã sắp xong

So sánh0

Hoán đổi0

Heapify0

Nhấn Chạy hoặc Bước kế...

🌳 Cây nhị phân (Binary Heap) — ánh xạ từ mảng

Ý tưởng

Heap Sort dựa trên cấu trúc dữ liệu Max-Heap — một cây nhị phân hoàn chỉnh trong đó mỗi node ≥ tất cả con của nó. Mảng ánh xạ thành cây: node i có con trái 2i+1, con phải 2i+2, cha (i-1)/2.

Hai giai đoạn chính:

Build Max-Heap: Chạy heapify từ node giữa trở về gốc (i = n/2-1 xuống 0). Độ phức tạp: O(n).
Extract & Sort: Lặp n-1 lần: hoán đổi gốc (lớn nhất) với phần tử cuối, giảm heap size, gọi heapify lại gốc. Độ phức tạp: O(n log n).

💡

Điểm mạnh của Heap Sort: Đảm bảo O(n log n) trong mọi trường hợp (không có worst-case O(n²) như Quick Sort). Không cần bộ nhớ phụ (O(1) in-place). Tuy nhiên, cache performance kém hơn Quick Sort trong thực tế.

Cài đặt C

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Heapify subtree gốc tại i, heap size = n */
void heapify(int a[], int n, int i) {
    int largest = i;       /* giả sử root là lớn nhất */
    int left    = 2*i + 1;
    int right   = 2*i + 2;

    if (left  < n && a[left]  > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;

    if (largest != i) {
        swap(&a[i], &a[largest]);
        heapify(a, n, largest); /* đệ quy xuống */
    }
}

void heapSort(int a[], int n) {
    /* Bước 1: Build Max-Heap từ mảng — O(n) */
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(a, n, i);

    /* Bước 2: Trích xuất lần lượt phần tử lớn nhất */
    for (int i = n - 1; i > 0; i--) {
        swap(&a[0], &a[i]); /* root (max) → cuối */
        heapify(a, i, 0);   /* khôi phục heap */
    }
}

int main() {
    int a[] = {4, 10, 3, 5, 1, 8, 7};
    int n = sizeof(a) / sizeof(a[0]);
    heapSort(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    /* Output: 1 3 4 5 7 8 10 */
    return 0;
}

Cấu trúc Max-Heap qua ví dụ

Với mảng [4, 10, 3, 5, 1, 8, 7], sau khi Build Max-Heap:

              10         ← index 0 (root, max)
           /       \
         5           8   ← index 1, 2
        / \         / \
       4   1       3   7 ← index 3,4,5,6

Mảng: [10, 5, 8, 4, 1, 3, 7]
       ↑root              ↑leaf

Độ phức tạp

Giai đoạn	Thời gian	Ghi chú
Build Max-Heap	O(n)	Chứng minh bằng geometric series
Extract n lần	O(n log n)	Mỗi lần extract + heapify = O(log n)
Tổng — Tốt nhất	O(n log n)	—
Tổng — Trung bình	O(n log n)	—
Tổng — Tệ nhất	O(n log n)	Không có worst case O(n²)
Không gian	O(1)	In-place, không cần bộ nhớ phụ

So sánh Quick Sort vs Heap Sort

	Quick Sort	Heap Sort
Trung bình	O(n log n) nhanh hơn	O(n log n)
Tệ nhất	O(n²)	O(n log n) ✓
Cache	Tốt (locality)	Kém hơn
Stable	Không	Không
In-place	O(log n) stack	O(1) ✓

← TrướcQuick Sort Tiếp →Linear Search