Heap nhị phân: hàng đợi ưu tiên, code và độ phức tạp

Heap giải quyết vấn đề gì

Nhiều chương trình liên tục cần phần tử khẩn cấp nhất từ một tập thay đổi: sự kiện kế tiếp trong mô phỏng, node chưa thăm gần nhất trong thuật toán Dijkstra, tác vụ có ưu tiên cao nhất, hoặc k giá trị lớn nhất trong một luồng dữ liệu. Sắp xếp lại cả tập sau mỗi lần chèn tốn O(n log n) mỗi lần. Danh sách đã sắp xếp lấy ra rẻ nhưng chèn O(n). Heap làm cả chèn và lấy phần tử nhỏ nhất đều O(log n), đúng thứ hàng đợi ưu tiên cần.

Ý tưởng: một cây lưu trong mảng

Heap là cây nhị phân đầy đủ: mọi tầng đều đầy trừ có thể tầng cuối, được lấp từ trái sang. Hình dạng đó cho phép lưu cây trong một list thường mà không cần con trỏ.

Hai thao tác sửa chữa giữ tính chất heap. Sift up: sau khi thêm phần tử mới vào cuối, hoán đổi nó với cha chừng nào nó còn nhỏ hơn. Sift down: sau khi chuyển phần tử cuối lên gốc, hoán đổi nó với con nhỏ hơn chừng nào nó còn lớn hơn con đó. Mỗi thao tác đi dọc một đường từ gốc tới lá, nên thực hiện tối đa khoảng log2(n) lần hoán đổi.

Ví dụ minh họa: push và pop

Bắt đầu với min-heap [2, 5, 3, 9, 6] (2 là gốc, các con của nó là 5 và 3, và 5 có các con là 9 và 6).

1. Push 1: thêm vào cuối, được [2, 5, 3, 9, 6, 1]. Chỉ số 5 có cha ở chỉ số 2 (giá trị 3).
2. 1 nhỏ hơn 3, hoán đổi: [2, 5, 1, 9, 6, 3]. Giờ chỉ số 2 có cha ở chỉ số 0 (giá trị 2).
3. 1 nhỏ hơn 2, hoán đổi: [1, 5, 2, 9, 6, 3]. Nó đã lên gốc, dừng.
4. Pop: lấy gốc 1 ra, chuyển phần tử cuối 3 lên gốc: [3, 5, 2, 9, 6].
5. Các con của gốc là 5 và 2; con nhỏ hơn là 2, và 3 lớn hơn, hoán đổi: [2, 5, 3, 9, 6]. Chỉ số 2 không có con, dừng. Lần pop trả về 1.

Cài đặt min-heap bằng Python

Lớp này cho thấy cơ chế hoạt động. Trong code thực tế hãy dùng heapq, trình bày ở phần sau.

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

Hàng đợi ưu tiên với heapq của Python

Mô-đun heapq làm việc trên list thông thường và luôn giữ nó là min-heap. heapify biến một list có sẵn thành heap tại chỗ trong O(n). Để dùng độ ưu tiên, hãy push các tuple: Python so sánh tuple từng phần tử, nên phần tử đầu là độ ưu tiên. Thêm một bộ đếm làm tiêu chí phân định khi bằng nhau để các phần tử cùng độ ưu tiên không bao giờ phải so sánh trực tiếp.

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

Với max-heap, Python 3.14 thêm heapq.heapify_max, heapq.heappush_max và heapq.heappop_max. Trên các phiên bản cũ hơn, mẹo thường dùng là push khóa đã đổi dấu, ví dụ heapq.heappush(h, -score), và đổi dấu lại khi pop.

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

Xây heap bằng cách gọi push n lần tốn O(n log n). heapify sift down từ cha cuối cùng tới gốc và tốn O(n), nên hãy ưu tiên dùng khi bạn đã có đủ phần tử.

Các biến thể và lỗi thường gặp

• Max-heap: cùng code nhưng đảo phép so sánh; trong Python, dùng các hàm _max (từ 3.14) hoặc đổi dấu khóa.
• Heap d-ary: mỗi node có d con. Cây nông hơn làm push rẻ hơn và pop đắt hơn một chút.
• Hàng đợi ưu tiên có chỉ mục / decrease-key: heapq không thể đổi độ ưu tiên của một phần tử tại chỗ. Cách né thường dùng (trong thuật toán Dijkstra) là push một mục mới và bỏ qua các mục lỗi thời khi chúng được pop ra.
• So sánh các phần tử không so sánh được: push (priority, dict) gây TypeError khi hai độ ưu tiên bằng nhau, vì khi đó Python so sánh các dict. Hãy thêm bộ đếm làm phần tử thứ hai của tuple.
• Coi list heap là đã sắp xếp. Chỉ heap[0] được đảm bảo; hãy dùng sorted(heap) nếu cần mọi phần tử theo thứ tự.
• Lỗi lệch một đơn vị khi trộn công thức đánh số từ 1 (con là 2i và 2i + 1) trong sách giáo khoa với list Python đánh số từ 0.

Khi nào dùng heap và các bài toán điển hình

Dùng heap khi bạn liên tục chỉ cần phần tử nhỏ nhất hoặc lớn nhất từ một tập luôn thay đổi. Dùng danh sách đã sắp xếp hoặc cây cân bằng khi còn cần duyệt theo thứ tự hoặc xóa tùy ý, và dùng min() thông thường khi chỉ cần giá trị nhỏ nhất một lần.

Ứng dụng kinh điển: đường đi ngắn nhất Dijkstra và cây khung nhỏ nhất Prim, gộp k danh sách đã sắp xếp (heapq.merge), tìm k phần tử lớn nhất hoặc nhỏ nhất (giữ heap kích thước k, O(n log k)), trung vị chạy (hai heap), bộ lập lịch tác vụ và mô phỏng hướng sự kiện, và heapsort.