heapq trong Python: heap và hàng đợi ưu tiên
Bài 5/25 · Chương 19
Thư viện chuẩn thường dùng
- 6 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Heap trong Python là một list được xếp theo quy tắc riêng để phần tử nhỏ nhất nằm ở đầu, nhờ module heapq. Bạn dùng heap khi cần lấy ra phần tử nhỏ nhất nhiều lần trong lúc dữ liệu vẫn được thêm vào, như một hàng đợi ưu tiên: đơn gấp được giao trước, đơn thường chờ sau.
Cần biết trước: sắp xếp list, tuple và lambda.
Heap là gì: phần tử nhỏ nhất đứng đầu
heapq.heapify(ds) xếp lại list ds tại chỗ thành một heap. Sau đó ds[0] là phần tử nhỏ nhất, nhưng phần còn lại của list chưa được sắp xếp hết.
import heapq
gia = [35000, 29000, 45000, 32000]
heapq.heapify(gia)
print(gia)
print(gia[0])KẾT QUẢ
[29000, 32000, 45000, 35000]
29000Heap chỉ hứa một điều: mỗi phần tử ở vị trí i không lớn hơn hai phần tử ở vị trí 2*i + 1 và 2*i + 2. Nhìn theo cách đó, list là một cây nhị phân mà gốc là ds[0], bài cây nhị phân kể về kiểu cây này. Vì chỉ giữ quy tắc ấy, heapq thêm hay lấy một phần tử chỉ phải đổi chỗ vài lần, kể cả khi list có hàng triệu phần tử. Đổi 35000 thành 25000 rồi chạy lại: dòng cuối in 25000.
Module heapq làm việc trên list thường, nên điều cần nhớ là chỉ sửa heap qua các hàm của module.
Thêm và lấy bằng heappush() và heappop()
heapq.heappush(h, x) thêm x vào heap h mà vẫn giữ quy tắc heap. heapq.heappop(h) lấy ra và trả về phần tử nhỏ nhất. Lấy hết từng phần tử một bằng vòng lặp while cho ra dãy tăng dần.
import heapq
h = []
for gia in [32000, 45000, 29000, 35000]:
heapq.heappush(h, gia)
print(h[0], len(h))
while h:
print(heapq.heappop(h))KẾT QUẢ
29000 4
29000
32000
35000
45000Muốn lấy phần tử lớn nhất trước, bạn đổi dấu khi thêm và đổi lại khi lấy ra: heappush(h, -gia), rồi -heappop(h).
Hàng đợi ưu tiên với tuple
Hàng đợi ưu tiên (priority queue) là hàng chờ mà phần tử có mức ưu tiên cao được lấy ra trước, bất kể đến lúc nào. Với heapq, bạn đẩy vào tuple (mức, thứ tự đến, dữ liệu): tuple so từng phần tử từ trái sang, nên mức nhỏ ra trước, cùng mức thì đơn đến trước ra trước.
import heapq
hang_cho = []
cac_don = [("DH1024", 2), ("DH1025", 1),
("DH1026", 2), ("DH1027", 1)]
for stt, (ma, muc) in enumerate(cac_don):
heapq.heappush(hang_cho, (muc, stt, ma))
while hang_cho:
muc, stt, ma = heapq.heappop(hang_cho)
print(ma, "mức", muc)KẾT QUẢ
DH1025 mức 1
DH1027 mức 1
DH1024 mức 2
DH1026 mức 2Ở đây mức 1 là gấp nhất. Số stt đứng giữa có hai việc: giữ thứ tự đến cho các đơn cùng mức, và chặn không cho phép so đi tới phần tử thứ ba. Đổi ("DH1027", 1) thành ("DH1027", 3) rồi chạy lại: dòng cuối in DH1027 mức 3.
Tìm N phần tử lớn nhất bằng nlargest()
heapq.nlargest(n, dãy) trả về list n phần tử lớn nhất, xếp từ lớn xuống. heapq.nsmallest(n, dãy) làm điều ngược lại. Cả hai nhận key= như sorted(), nên bạn chọn được tiêu chí so bằng một lambda.
import heapq
menu = {"cà phê sữa": 29000, "bạc xỉu": 32000,
"trà đào": 35000, "sinh tố bơ": 45000}
print(heapq.nlargest(2, menu, key=lambda mon: menu[mon]))
re_nhat = heapq.nsmallest(1, menu.items(), key=lambda cap: cap[1])
print(re_nhat)
print(heapq.nlargest(2, [3, 1, 4, 1, 5]))KẾT QUẢ
['sinh tố bơ', 'trà đào']
[('cà phê sữa', 29000)]
[5, 4]Kết quả giống sorted(..., reverse=True)[:n] của bài sắp xếp. nlargest() hợp khi n nhỏ so với dãy dài, vì nó không cần sắp xếp cả dãy. Khi n bằng 1, max() và min() là đủ.
Kiểm tra nhanh
Sau
import heapq,h = [7, 3, 9, 1]vàheapq.heapify(h),h[0]bằng bao nhiêu?719
Sau
import heapq,h = [1, 5, 9]vàh.append(0),heapq.heappop(h)trả về gì?01- Báo lỗi
ValueError
Với
import heapqvàds = [3, 1, 4, 1, 5], những biểu thức nào bằngTrue?heapq.nlargest(2, ds) == [5, 4]heapq.nsmallest(2, ds) == [1, 3]heapq.nsmallest(1, ds) == [min(ds)]heapq.nlargest(2, ds) == [4, 5]
Sau
import heapqvàh = [(1, {"a": 1})],heapq.heappush(h, (1, {"b": 2}))báo lỗi gì?- Báo lỗi
TypeError - Báo lỗi
KeyError - Báo lỗi
ValueError
- Báo lỗi
Bài tập
Giao đơn gấp trước
Viết hàm xu_ly(cac_lenh) đi qua list cac_lenh theo thứ tự. Mỗi lệnh là một trong hai dạng:
Tuple
(mã đơn, mức), như("DH1024", 2): thêm đơn vào hàng chờ. Mức1là gấp nhất.Chuỗi
"GIAO": lấy ra đơn có mức nhỏ nhất, cùng mức thì đơn thêm vào trước. Hàng chờ rỗng thì bỏ qua.
Dùng heapq.heappush() và heapq.heappop(). Hàm không sửa cac_lenh.
Ví dụ: xu_ly([("DH1024", 2), ("DH1025", 1), "GIAO"]) trả về ["DH1025"].
Trả về: mã các đơn đã giao theo thứ tự giao, một list.
import heapq
def xu_ly(cac_lenh):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Heap là list mà
h[0]là phần tử nhỏ nhất, phần còn lại chưa sắp xếp hết.heapify()xếp list có sẵn,heappush()thêm,heappop()lấy phần tử nhỏ nhất ra.Thêm bằng
append()làm hỏng heap mà không báo lỗi.Hàng đợi ưu tiên đẩy vào
(mức, thứ tự đến, dữ liệu), để cùng mức thì ra theo thứ tự đến và không phải so dữ liệu.nlargest(n, ...)vànsmallest(n, ...)lấynphần tử đầu, cókey=.
Câu hỏi thường gặp
Min heap trong Python có sẵn, còn max heap thì sao?
heapq là min heap: heappop() lấy phần tử nhỏ nhất. Cách chạy được trên 3.12 tới 3.14 là đổi dấu số khi thêm và khi lấy. Python 3.14 có thêm heapq.heappush_max() và heapq.heappop_max(), còn 3.12 và 3.13 chưa có hai hàm này.
Hàng đợi ưu tiên (priority queue) trong Python nên dựng bằng heapq hay sắp xếp lại list?
Sắp xếp lại cả list sau mỗi lần thêm đơn thì chậm dần khi hàng dài ra. heappush() và heappop() chỉ đổi chỗ vài phần tử mỗi lần, nên hợp với hàng chờ vừa thêm vừa lấy liên tục. Chỉ sắp xếp một lần rồi đọc hết thì dùng sort() là đủ.
Vì sao in heap ra thấy các số không theo thứ tự?
Heap chỉ bảo đảm phần tử đầu nhỏ nhất, mỗi phần tử không lớn hơn hai phần tử con của nó. Muốn thấy dãy tăng dần, bạn gọi heappop() lần lượt hoặc dùng sorted(h), hàm này trả về list mới và không đổi h.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.