2.38. Hàng đợi ưu tiên

Hàng đợi ưu tiên là một container luôn biết phần tử nào nhỏ nhất (hoặc lớn nhất) trong số các phần tử của nó mà không cần sắp xếp toàn bộ. heapq triển khai điều này trong MicroPython sử dụng một list thông thường làm bộ lưu trữ và một thuật toán dựa trên cây gọi là min-heap để giữ phần tử nhỏ nhất tại chỉ số 0.

2.38.1. Mô hình tư duy

Min-heap là một danh sách được sắp xếp sao cho phần tử tại mọi chỉ số đều nhỏ hơn hoặc bằng các phần tử tại chỉ số 2*i + 1 và 2*i + 2. Cách sắp xếp này làm cho ba thao tác trở nên nhanh chóng:

  • Tìm phần tử nhỏ nhất -- nó nằm tại heap[0]. Chỉ cần một lần tra cứu chỉ số, không cần duyệt toàn bộ.

  • Thêm một phần tử -- nó nổi lên qua cây, so sánh với một cha mẹ mỗi cấp. Một nghìn phần tử chỉ cần khoảng mười lần so sánh; một triệu phần tử chỉ khoảng hai mươi.

  • Xóa phần tử nhỏ nhất -- cùng quá trình duyệt theo chiều ngược lại, với cùng số lần so sánh nhỏ.

Danh sách không được sắp xếp. Duyệt qua nó cho các phần tử theo thứ tự tùy ý. Chỉ heap[0] được đảm bảo là giá trị nhỏ nhất.

2.38.2. Ba hàm trong MicroPython

Mô-đun heapq của MicroPython chỉ cung cấp đúng ba hàm:

  • heapq.heappush() -- chèn một phần tử, giữ nguyên bất biến của heap.

  • heapq.heappop() -- xóa và trả về phần tử nhỏ nhất.

  • heapq.heapify() -- sắp xếp lại một danh sách hiện có thành heap tại chỗ.

Đó là toàn bộ giao diện. Các hàm heappushpop, heapreplace, nlargest, nsmallest và merge của CPython không tồn tại; các mẫu dưới đây cho thấy cách xây dựng các hàm phổ biến theo cách thủ công.

Bắt đầu từ đầu:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

Bắt đầu từ dữ liệu hiện có:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Heapify chạm vào mỗi phần tử một lần và nhanh hơn đáng kể so với việc đẩy từng phần tử một lần.

2.38.3. Top-N trên một luồng dữ liệu

Một ứng dụng tự nhiên của hàng đợi ưu tiên: theo dõi N phần tử lớn nhất trong một luồng chỉ đọc được một lần.

Mẹo là giữ một min-heap kích thước N. Mỗi giá trị mới được đẩy vào; nếu heap vượt quá N phần tử, loại bỏ phần tử nhỏ nhất. Phần tử nhỏ nhất luôn ở heap[0], vì vậy một phép so sánh duy nhất quyết định giữ hay loại bỏ mỗi giá trị đến:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

Heap không bao giờ vượt quá N phần tử, vì vậy mỗi giá trị đến tốn cùng số lần so sánh nhỏ dù luồng dài đến đâu. Bước sorted cuối cùng là bước duy nhất có chi phí phụ thuộc trực tiếp vào N.

2.38.4. Sự kiện được lên lịch

Hàng đợi ưu tiên gồm các bộ (deadline, payload) là dạng chuẩn cho một bộ lập lịch sự kiện. Các bộ được so sánh theo thứ tự từ điển, vì vậy bộ có deadline nhỏ nhất tự động nổi lên đầu:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

Nếu hai sự kiện cùng deadline, phép so sánh bộ chuyển sang phần tử thứ hai. Đối với các payload không tự nhiên có thể so sánh, thêm một bộ đếm làm phần tử thứ hai của bộ để đảm bảo thứ tự ổn định:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Bây giờ hành vi ưu tiên-deadline-nhỏ-nhất vẫn còn nguyên, các trường hợp hòa được phá vỡ theo bộ đếm để các tác vụ được lên lịch trước chạy trước, và task không cần phải có thể so sánh được.

2.38.5. Những gì heapq không cung cấp

Một số mẫu trông như thể nên hoạt động, nhưng thực ra không:

  • Duyệt for x in heap không cho đầu ra đã được sắp xếp -- thứ tự cơ bản của danh sách là bố cục cây của heap. Để tiêu thụ heap theo thứ tự, hãy dùng heappop cho đến khi trống.

  • Không có cách nào để thay đổi độ ưu tiên của một phần tử đã có trong heap. Cách giải quyết tiêu chuẩn là đẩy độ ưu tiên mới như một mục mới và đánh dấu mục cũ là đã hủy (bỏ qua khi nó được lấy ra).

  • Heap lưu trữ các tham chiếu đến các phần tử của nó, không phải bản sao. Thay đổi một phần tử sau khi đã đẩy có thể phá vỡ bất biến của heap. Hãy sử dụng các giá trị bất biến (số, bộ) làm khóa so sánh.

Min-heap trên một danh sách thông thường là công cụ phù hợp cho bất kỳ câu hỏi "phần tử nào nhỏ nhất" hay "cái gì khẩn cấp nhất" trên một thiết bị nhúng nhỏ. Ba hàm, một danh sách, và heap sẽ lo phần còn lại.