Cấu trúc dữ liệu heap (đống) có thể dùng để biểu diễn hàng đợi ưu tiên (priority queue). Trong Python nó có sẵn trong module heapq. Ở đây nó tạo min-heap (đống nhỏ nhất). Vì vậy khi độ ưu tiên là 1, nó đại diện cho ưu tiên cao nhất. Khi chèn phần tử mới, cấu trúc heap tự cập nhật.
Để dùng module này, nên nhập bằng:
import heapq
Có một số thao tác liên quan đến heap:
Phương thức heapq.heapify(iterable)
Chuyển đổi một tập dữ liệu iterable thành cấu trúc dữ liệu heap.
Phương thức heapq.heappush(heap, element)
Chèn phần tử vào heap. Sau đó re-heap (cân bằng lại) toàn bộ cấu trúc heap.
Phương thức heapq.heappop(heap)
Trả về và xóa phần tử từ đỉnh heap (phần tử nhỏ nhất) và thực hiện heapify trên các phần tử còn lại.
Phương thức heapq.heappushpop(heap, element)
Chèn và pop phần tử trong một câu lệnh.
Phương thức heapq.heapreplace(heap, element)
Chèn và pop phần tử trong một câu lệnh. Nó xóa phần tử từ gốc heap, sau đó chèn phần tử mới vào heap.
Phương thức heapq.nlargest(n, iterable, key=None)
Trả về n phần tử lớn nhất từ heap.
Phương thức heapq.nsmallest(n, iterable, key=None)
Trả về n phần tử nhỏ nhất từ heap.
Mã ví dụ
import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Phần tử Popped: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)
Kết quả
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] [7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19] Phần tử Popped: 7 [10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] [89, 65, 58, 41]