heapq --- Thuật toán xếp hàng đống

Source code: Lib/heapq.py

Mô-đun này cung cấp cách triển khai thuật toán hàng đợi đống, còn được gọi là thuật toán hàng đợi ưu tiên.

Đống tối thiểu là cây nhị phân mà mỗi nút cha có giá trị nhỏ hơn hoặc bằng bất kỳ nút con nào của nó. Chúng tôi gọi điều kiện này là bất biến heap.

Đối với các vùng heap tối thiểu, việc triển khai này sử dụng các danh sách có heap[k] <= heap[2*k+1] và heap[k] <= heap[2*k+2] cho tất cả k có các phần tử được so sánh tồn tại. Các phần tử được tính từ số 0. Thuộc tính thú vị của min-heap là phần tử nhỏ nhất của nó luôn là gốc, heap[0].

Heap tối đa thỏa mãn bất biến ngược: mọi nút cha đều có giá trị greater hơn bất kỳ nút con nào của nó. Chúng được triển khai dưới dạng danh sách maxheap[2*k+1] <= maxheap[k] và maxheap[2*k+2] <= maxheap[k] cho tất cả k có các phần tử được so sánh tồn tại. Gốc, maxheap[0], chứa phần tử largest; heap.sort(reverse=True) duy trì bất biến heap tối đa.

heapq API khác với thuật toán heap trong sách giáo khoa ở hai khía cạnh: (a) Chúng tôi sử dụng lập chỉ mục dựa trên 0. Điều này làm cho mối quan hệ giữa chỉ mục cho một nút và các chỉ mục cho nút con của nó ít rõ ràng hơn một chút, nhưng phù hợp hơn vì Python sử dụng lập chỉ mục dựa trên 0. (b) Sách giáo khoa thường tập trung vào vùng heap tối đa do tính phù hợp của chúng cho việc sắp xếp tại chỗ. Việc triển khai của chúng tôi ưu tiên các vùng heap tối thiểu vì chúng tương ứng tốt hơn với Python lists.

Hai khía cạnh này giúp bạn có thể xem vùng heap như một danh sách Python thông thường mà không có gì đáng ngạc nhiên: heap[0] là mục nhỏ nhất và heap.sort() duy trì sự bất biến của vùng heap!

Giống như list.sort(), cách triển khai này chỉ sử dụng toán tử < để so sánh, cho cả vùng heap tối thiểu và vùng heap tối đa.

Trong API bên dưới và trong tài liệu này, thuật ngữ không đủ tiêu chuẩn heap thường đề cập đến một vùng nhớ tối thiểu. Zz003zz cho vùng heap tối đa được đặt tên bằng hậu tố _max.

Để tạo vùng nhớ heap, hãy sử dụng danh sách được khởi tạo dưới dạng [] hoặc chuyển đổi danh sách hiện có thành vùng heap tối thiểu hoặc vùng heap tối đa bằng cách sử dụng các hàm heapify() hoặc heapify_max() tương ứng.

Các chức năng sau được cung cấp cho vùng heap tối thiểu:

heapq.heapify(x)

Chuyển đổi danh sách x thành một đống tối thiểu, tại chỗ, theo thời gian tuyến tính.

heapq.heappush(heap, item)

Đẩy giá trị item lên heap, duy trì bất biến min-heap.

heapq.heappop(heap)

Bật và trả lại phần tử nhỏ nhất từ heap, duy trì tính bất biến của vùng heap tối thiểu. Nếu heap trống, IndexError sẽ được nâng lên. Để truy cập mục nhỏ nhất mà không cần bật nó lên, hãy sử dụng heap[0].

heapq.heappushpop(heap, item)

Đẩy item lên heap, sau đó bật và trả lại phần tử nhỏ nhất từ heap. Hành động kết hợp chạy hiệu quả hơn heappush(), sau đó là lệnh gọi riêng tới heappop().

heapq.heapreplace(heap, item)

Bật và trả lại mục nhỏ nhất từ heap, đồng thời đẩy item mới. Kích thước heap không thay đổi. Nếu heap trống, IndexError sẽ được nâng lên.

Thao tác một bước này hiệu quả hơn so với heappop(), theo sau là heappush() và có thể phù hợp hơn khi sử dụng vùng nhớ heap có kích thước cố định. Sự kết hợp pop/push luôn trả về một phần tử từ heap và thay thế nó bằng item.

Giá trị được trả về có thể lớn hơn item được thêm vào. Nếu không muốn, hãy cân nhắc sử dụng heappushpop(). Sự kết hợp push/pop của nó trả về giá trị nhỏ hơn trong hai giá trị, để lại giá trị lớn hơn trong heap.

Đối với vùng heap tối đa, các chức năng sau được cung cấp:

heapq.heapify_max(x)

Chuyển đổi danh sách x thành vùng heap tối đa, tại chỗ, theo thời gian tuyến tính.

Added in version 3.14.

heapq.heappush_max(heap, item)

Đẩy giá trị item lên heap heap tối đa, duy trì bất biến heap tối đa.

Added in version 3.14.

heapq.heappop_max(heap)

Bật và trả lại mục lớn nhất từ heap heap tối đa, duy trì tính bất biến của heap tối đa. Nếu vùng heap tối đa trống, IndexError sẽ được nâng lên. Để truy cập mục lớn nhất mà không cần bật nó, hãy sử dụng maxheap[0].

Added in version 3.14.

heapq.heappushpop_max(heap, item)

Đẩy item trên heap heap tối đa, sau đó bật và trả lại mục lớn nhất từ heap. Hành động kết hợp chạy hiệu quả hơn heappush_max(), sau đó là lệnh gọi riêng tới heappop_max().

Added in version 3.14.

heapq.heapreplace_max(heap, item)

Bật và trả lại mục lớn nhất từ heap heap tối đa, đồng thời đẩy item mới. Kích thước heap tối đa không thay đổi. Nếu vùng heap tối đa trống, IndexError sẽ được nâng lên.

Giá trị trả về có thể nhỏ hơn item được thêm vào. Tham khảo chức năng tương tự heapreplace() để biết ghi chú sử dụng chi tiết.

Added in version 3.14.

Mô-đun này cũng cung cấp ba chức năng có mục đích chung dựa trên vùng heap.

heapq.merge(*iterables, key=None, reverse=False)

Hợp nhất nhiều đầu vào được sắp xếp thành một đầu ra được sắp xếp duy nhất (ví dụ: hợp nhất các mục nhập có dấu thời gian từ nhiều tệp nhật ký). Trả về iterator trên các giá trị được sắp xếp.

Tương tự như sorted(itertools.chain(*iterables)) nhưng trả về một lần lặp, không kéo dữ liệu vào bộ nhớ cùng một lúc và giả định rằng mỗi luồng đầu vào đã được sắp xếp (nhỏ nhất đến lớn nhất).

Có hai đối số tùy chọn phải được chỉ định làm đối số từ khóa.

key chỉ định key function của một đối số được sử dụng để trích xuất khóa so sánh từ mỗi phần tử đầu vào. Giá trị mặc định là None (so sánh trực tiếp các phần tử).

reverse là giá trị boolean. Nếu được đặt thành True thì các phần tử đầu vào sẽ được hợp nhất như thể mỗi phép so sánh được đảo ngược. Để đạt được hành vi tương tự như sorted(itertools.chain(*iterables), reverse=True), tất cả các lần lặp phải được sắp xếp từ lớn nhất đến nhỏ nhất.

Thay đổi trong phiên bản 3.5: Đã thêm các tham số key và reverse tùy chọn.

heapq.nlargest(n, iterable, key=None)

Trả về danh sách có phần tử lớn nhất n từ tập dữ liệu được xác định bởi iterable. key, nếu được cung cấp, sẽ chỉ định hàm của một đối số được sử dụng để trích xuất khóa so sánh từ mỗi phần tử trong iterable (ví dụ: key=str.lower). Tương đương với: sorted(iterable, key=key, reverse=True)[:n].

heapq.nsmallest(n, iterable, key=None)

Trả về danh sách có các phần tử nhỏ nhất n từ tập dữ liệu được xác định bởi iterable. key, nếu được cung cấp, sẽ chỉ định hàm của một đối số được sử dụng để trích xuất khóa so sánh từ mỗi phần tử trong iterable (ví dụ: key=str.lower). Tương đương với: sorted(iterable, key=key)[:n].

Hai hàm sau hoạt động tốt nhất với các giá trị nhỏ hơn của n. Đối với các giá trị lớn hơn, việc sử dụng hàm sorted() sẽ hiệu quả hơn. Ngoài ra, khi n==1, sẽ hiệu quả hơn khi sử dụng các hàm min() và max() tích hợp sẵn. Nếu cần phải sử dụng nhiều lần các hàm này, hãy cân nhắc việc biến iterable thành một heap thực sự.

Ví dụ cơ bản

Một heapsort có thể được triển khai bằng cách đẩy tất cả các giá trị vào một đống và sau đó bật ra từng giá trị nhỏ nhất:

>>> def heapsort(iterable):
... h = []
... cho giá trị có thể lặp lại:
... heapush(h, giá trị)
... return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Điều này tương tự như sorted(iterable), nhưng không giống như sorted(), cách triển khai này không ổn định.

Các phần tử heap có thể là các bộ dữ liệu. Điều này hữu ích khi gán các giá trị so sánh (chẳng hạn như mức độ ưu tiên của nhiệm vụ) cùng với bản ghi chính đang được theo dõi:

>>> h = []
>>> Heappush(h, (5, 'viết mã'))
>>> Heappush(h, (7, 'phát hành sản phẩm'))
>>> Heappush(h, (1, 'viết thông số'))
>>> Heappush(h, (3, 'tạo bài kiểm tra'))
>>> heappop(h)
(1, 'viết thông số kỹ thuật')

Ứng dụng khác

Medians là thước đo xu hướng trung tâm của một tập hợp số. Trong các phân phối bị lệch bởi các giá trị ngoại lệ, giá trị trung vị cung cấp ước tính ổn định hơn giá trị trung bình (trung bình số học). Trung vị đang chạy là online algorithm cập nhật liên tục khi có dữ liệu mới.

Trung vị đang chạy có thể được triển khai một cách hiệu quả bằng cách cân bằng hai vùng heap, vùng heap tối đa cho các giá trị bằng hoặc dưới điểm giữa và vùng heap tối thiểu cho các giá trị trên điểm giữa. Khi hai đống có cùng kích thước thì trung vị mới là trung bình cộng của các đỉnh của hai đống; mặt khác, số trung vị nằm ở đầu vùng heap lớn hơn:

chắc chắn đang chạy_median (có thể lặp lại):
    " Mang lại giá trị trung bình tích lũy được thấy cho đến nay."

    lo = [] # max-heap
    hi = [] # min-heap (cùng kích thước hoặc nhỏ hơn lo một cái)

    cho x trong lần lặp:
        nếu len(lo) == len(hi):
            heappush_max(lo, heappushpop(hi, x))
            năng suất lo[0]
        khác:
            heappush(xin chào, heappushpop_max(lo, x))
            năng suất (lo[0] + hi[0]) / 2

Ví dụ:

>>> danh sách(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
[5.0, 7.0, 5.0, 7.0, 8.0, 8.5]

Ghi chú triển khai hàng ưu tiên

priority queue được sử dụng phổ biến cho một đống và nó đưa ra một số thách thức khi triển khai:

  • Tính ổn định của sắp xếp: làm cách nào để bạn có thể trả về hai tác vụ có mức độ ưu tiên như nhau theo thứ tự chúng được thêm vào ban đầu?

  • Ngắt so sánh bộ dữ liệu cho các cặp (mức độ ưu tiên, nhiệm vụ) nếu mức độ ưu tiên bằng nhau và các nhiệm vụ không có thứ tự so sánh mặc định.

  • Nếu mức độ ưu tiên của một tác vụ thay đổi, bạn làm cách nào để di chuyển nó sang vị trí mới trong vùng nhớ heap?

  • Hoặc nếu một tác vụ đang chờ xử lý cần được xóa, bạn làm cách nào để tìm nó và xóa nó khỏi hàng đợi?

Giải pháp cho hai thách thức đầu tiên là lưu trữ các mục dưới dạng danh sách 3 thành phần bao gồm mức độ ưu tiên, số lượng mục nhập và nhiệm vụ. Số lượng mục nhập đóng vai trò là yếu tố quyết định để hai nhiệm vụ có cùng mức độ ưu tiên được trả về theo thứ tự chúng được thêm vào. Và vì không có hai mục nhập nào giống nhau nên việc so sánh bộ dữ liệu sẽ không bao giờ cố gắng so sánh trực tiếp hai nhiệm vụ.

Một giải pháp khác cho vấn đề về các tác vụ không thể so sánh được là tạo một lớp trình bao bọc bỏ qua mục tác vụ và chỉ so sánh trường ưu tiên

từ các lớp dữ liệu nhập lớp dữ liệu, trường
từ việc nhập nhập Bất kỳ

@dataclass(thứ tự=True)
lớp Ưu tiên:
    mức độ ưu tiên: int
    mục: Any=field(so sánh=False)

Những thách thức còn lại xoay quanh việc tìm kiếm một nhiệm vụ đang chờ xử lý và thực hiện các thay đổi về mức độ ưu tiên của nó hoặc loại bỏ nó hoàn toàn. Việc tìm kiếm một tác vụ có thể được thực hiện bằng cách sử dụng từ điển trỏ đến một mục trong hàng đợi.

Việc loại bỏ mục nhập hoặc thay đổi mức độ ưu tiên của nó khó khăn hơn vì nó sẽ phá vỡ các bất biến cấu trúc heap. Vì vậy, giải pháp khả thi là đánh dấu mục nhập là đã xóa và thêm mục nhập mới với mức độ ưu tiên đã sửa đổi:

pq = [] # list các mục được sắp xếp thành một đống
entry_finder = {} # mapping nhiệm vụ cho các mục
REMOVED = '<removed-task>' # placeholder cho tác vụ đã xóa
bộ đếm = itertools.count() đếm chuỗi # unique

def add_task(tác vụ, mức độ ưu tiên=0):
    'Thêm nhiệm vụ mới hoặc cập nhật mức độ ưu tiên của nhiệm vụ hiện có'
    nếu tác vụ trong entry_finder:
        xóa_task(nhiệm vụ)
    đếm = tiếp theo (bộ đếm)
    entry = [ưu tiên, số lượng, nhiệm vụ]
    entry_finder[task] = mục nhập
    heapush(pq, mục nhập)

chắc chắn loại bỏ_task (tác vụ):
    'Đánh dấu tác vụ hiện có là REMOVED.  Tăng KeyError nếu không tìm thấy.'
    entry = entry_finder.pop(task)
    mục [-1] = REMOVED

chắc chắn pop_task():
    'Xóa và trả lại nhiệm vụ có mức độ ưu tiên thấp nhất. Tăng KeyError nếu trống.'
    trong khi pq:
        mức độ ưu tiên, số lượng, nhiệm vụ = heappop(pq)
        nếu nhiệm vụ không phải là REMOVED:
            del entry_finder[task]
            trả lại nhiệm vụ
    raise KeyError('pop từ hàng ưu tiên trống')

Lý thuyết

Đống là các mảng trong đó a[k] <= a[2*k+1] và a[k] <= a[2*k+2] cho tất cả k, đếm các phần tử từ 0. Để so sánh, các phần tử không tồn tại được coi là vô hạn. Thuộc tính thú vị của heap là a[0] luôn là phần tử nhỏ nhất của nó.

Bất biến kỳ lạ ở trên nhằm mục đích biểu diễn bộ nhớ hiệu quả cho một giải đấu. Các số bên dưới là k, không phải a[k]:

0

              1 2

      3 4 5 6

  7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Trong cây ở trên, mỗi ô k đứng đầu 2*k+1 và 2*k+2. Trong một giải đấu nhị phân thông thường mà chúng ta thấy trong thể thao, mỗi ô là người chiến thắng trên hai ô mà nó đứng đầu và chúng ta có thể theo dõi người chiến thắng dọc theo cây để xem tất cả các đối thủ mà người đó có. Tuy nhiên, trong nhiều ứng dụng máy tính của những giải đấu như vậy, chúng ta không cần theo dõi lịch sử của người chiến thắng. Để bộ nhớ hiệu quả hơn, khi một ô chiến thắng được thăng hạng, chúng tôi cố gắng thay thế nó bằng một ô khác ở cấp độ thấp hơn và quy tắc trở thành một ô và hai ô ở trên cùng chứa ba mục khác nhau, nhưng ô trên cùng "thắng" hai ô ở trên cùng.

Nếu bất biến vùng heap này luôn được bảo vệ thì chỉ số 0 rõ ràng là người chiến thắng chung cuộc. Cách thuật toán đơn giản nhất để loại bỏ nó và tìm ra người chiến thắng "tiếp theo" là di chuyển một số người thua cuộc (giả sử ô 30 trong sơ đồ ở trên) vào vị trí 0, sau đó thấm số 0 mới này xuống cây, trao đổi các giá trị cho đến khi bất biến được thiết lập lại. Đây rõ ràng là logarit của tổng số phần tử trong cây. Bằng cách lặp lại tất cả các mục, bạn sẽ có được sắp xếp O(n log n).

Một tính năng hay của loại này là bạn có thể chèn các mục mới một cách hiệu quả trong khi quá trình sắp xếp đang diễn ra, miễn là các mục được chèn không "tốt hơn" phần tử thứ 0 cuối cùng mà bạn đã trích xuất. Điều này đặc biệt hữu ích trong bối cảnh mô phỏng, trong đó cây chứa tất cả các sự kiện sắp đến và điều kiện "thắng" có nghĩa là thời gian dự kiến ​​nhỏ nhất. Khi một sự kiện lên lịch cho các sự kiện khác để thực hiện, chúng sẽ được lên lịch trong tương lai để chúng có thể dễ dàng đi vào vùng nhớ heap. Vì vậy, heap là một cấu trúc tốt để triển khai bộ lập lịch (đây là cấu trúc mà tôi đã sử dụng cho trình sắp xếp thứ tự MIDI của mình :-).

Các cấu trúc khác nhau để triển khai bộ lập lịch đã được nghiên cứu rộng rãi và heap rất tốt cho việc này vì chúng có tốc độ khá nhanh, tốc độ gần như không đổi và trường hợp xấu nhất không khác nhiều so với trường hợp trung bình. Tuy nhiên, có những cách biểu diễn khác hiệu quả hơn về tổng thể, tuy nhiên những trường hợp xấu nhất có thể rất khủng khiếp.

Heap cũng rất hữu ích trong các loại đĩa lớn. Có lẽ tất cả các bạn đều biết rằng một loại lớn có nghĩa là tạo ra các "chạy" (là các chuỗi được sắp xếp trước, có kích thước thường liên quan đến dung lượng bộ nhớ CPU), theo sau là một đường chuyền hợp nhất cho các lần chạy này, việc hợp nhất này thường được tổ chức rất khéo léo [1]. Điều rất quan trọng là việc sắp xếp ban đầu tạo ra thời gian chạy dài nhất có thể. Các giải đấu là một cách tốt để đạt được điều đó. Nếu sử dụng tất cả bộ nhớ có sẵn để tổ chức một giải đấu, bạn thay thế và chọn lọc các mục phù hợp với lượt chạy hiện tại, bạn sẽ tạo ra các lượt chạy có kích thước gấp đôi bộ nhớ cho đầu vào ngẫu nhiên và tốt hơn nhiều cho đầu vào được sắp xếp mờ.

Hơn nữa, nếu bạn xuất mục thứ 0 trên đĩa và nhận được đầu vào có thể không phù hợp với giải đấu hiện tại (vì giá trị "thắng" so với giá trị đầu ra cuối cùng), nó không thể vừa với heap, do đó kích thước của heap giảm. Bộ nhớ được giải phóng có thể được tái sử dụng một cách khéo léo ngay lập tức để dần dần xây dựng vùng nhớ thứ hai, vùng này phát triển với tốc độ chính xác như vùng heap thứ nhất đang tan chảy. Khi đống đầu tiên biến mất hoàn toàn, bạn chuyển đổi đống và bắt đầu lần chạy mới. Thông minh và khá hiệu quả!

Nói một cách dễ hiểu, heap là cấu trúc bộ nhớ hữu ích cần biết. Tôi sử dụng chúng trong một số ứng dụng và tôi nghĩ sẽ tốt hơn nếu giữ lại một mô-đun 'đống'. :-)

Chú thích cuối trang