Thuật toán sắp xếp vun đống: cách hoạt động, mã và độ phức tạp

Ý tưởng bằng lời đơn giản

Sắp xếp vun đống là sắp xếp chọn với cách tìm giá trị lớn nhất nhanh hơn. Sắp xếp chọn quét toàn bộ phần chưa sắp xếp, mỗi lần O(n). Sắp xếp vun đống giữ phần chưa sắp xếp dưới dạng đống, nên giá trị lớn nhất luôn ở chỉ số 0 và khôi phục thứ tự sau khi lấy nó ra chỉ tốn O(log n).

Đống nhị phân được lưu trong mảng thường, không cần con trỏ. Với phần tử ở chỉ số i:

• con trái ở 2*i + 1 và con phải ở 2*i + 2;
• nút cha ở (i - 1) // 2;
• trong max-heap, mỗi nút cha lớn hơn hoặc bằng các nút con, nên phần tử lớn nhất ở chỉ số 0.

1. Xây max-heap từ mảng bằng cách đẩy xuống (sift down) mọi nút không phải lá, bắt đầu từ nút cuối và đi về chỉ số 0.
2. Đổi gốc (giá trị lớn nhất) với phần tử cuối của đống. Phần tử đó giờ đã ở đúng chỗ cuối cùng.
3. Thu nhỏ đống đi một và đẩy gốc mới xuống cho đến khi tính chất đống được thỏa mãn trở lại.
4. Lặp lại bước 2 và 3 cho đến khi đống chỉ còn một phần tử.

Ví dụ minh họa từng bước

Sắp xếp [4, 10, 3, 5, 1]. Các phần tử sau dấu gạch đã được sắp xếp và cố định.

Cài đặt bằng Python

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Module heapq của Python cung cấp min-heap trên list thông thường. Lấy ra từng phần tử cho ra danh sách đã sắp xếp, đó là một bản sắp xếp vun đống ngắn gọn (không tại chỗ):

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

Độ phức tạp thời gian và không gian

Xây đống từ dưới lên là O(n), không phải O(n log n), vì tổng chiều cao các nút trong cây nhị phân đầy đủ là O(n). Giai đoạn lấy ra chiếm phần lớn tổng thời gian.

So sánh sắp xếp vun đống với các thuật toán khác

Sắp xếp vun đống không ổn định: việc đổi gốc xuống cuối có thể đưa một phần tử vượt qua các phần tử cùng khóa. Điểm mạnh chính là đảm bảo O(n log n) ở trường hợp xấu nhất cùng với O(1) không gian phụ, một sự kết hợp mà cả sắp xếp nhanh lẫn sắp xếp trộn đều không có. Điểm yếu là truy cập bộ nhớ: nhảy giữa chỉ số i và 2*i + 1 dùng bộ nhớ đệm CPU kém, nên thường chậm hơn sắp xếp nhanh được cài đặt tốt. Introsort dùng sắp xếp vun đống làm phương án dự phòng khi sắp xếp nhanh đệ quy quá sâu.

Biến thể và lỗi thường gặp

• Sắp xếp một phần: để chỉ lấy k phần tử lớn nhất, xây đống và lấy ra k lần, O(n + k log n). Trong Python, heapq.nlargest và heapq.nsmallest làm việc này.
• Top-k từ một luồng dữ liệu: giữ một min-heap kích thước k và đẩy vào hoặc thay thế từng phần tử mới, O(n log k) thời gian và O(k) bộ nhớ.
• Bottom-up heapsort đẩy “ô trống” xuống tận lá trước rồi mới đẩy lên, giúp tiết kiệm phép so sánh.
• Smoothsort, biến thể dựa trên đống của Dijkstra, chạy O(n) trên đầu vào đã sắp xếp nhưng ít được dùng vì phức tạp.

Khi nào nên dùng sắp xếp vun đống

Dùng sắp xếp vun đống khi cần đảm bảo O(n log n) ở trường hợp xấu nhất mà không thêm bộ nhớ, ví dụ trong hệ thống nhúng hoặc thời gian thực, hoặc làm phương án dự phòng an toàn bên trong thuật toán sắp xếp khác. Với mã Python hằng ngày, hãy dùng sorted(), ổn định và nhanh hơn trên dữ liệu điển hình. Bản thân đống hữu ích hơn việc sắp xếp: hàng đợi ưu tiên, đường đi ngắn nhất Dijkstra, bộ lập lịch, trộn k danh sách đã sắp xếp (heapq.merge) và tìm k giá trị lớn nhất đều dựa trên nó. Phỏng vấn thường hỏi công thức chỉ số của đống, vì sao xây đống là O(n), và bài toán top-k.