Giao diện
Hàng đợi ưu tiên
ưu tiên lấy phần tử dựa trên khóa ưu tiên, thay vì thời điểm thêm. Với min-priority queue, khóa nhỏ nhất được lấy trước. Heap là một cách cài đặt phổ biến, cho thêm và lấy phần tử ưu tiên trong .
Giải thích kỹ thuật
Heap không phải danh sách đã sắp xếp hoàn toàn. Min-heap giữ khóa của nút cha không lớn hơn khóa của các con. Do đó ở gốc. Các nút ở những nhánh khác nhau không nhất thiết có thứ tự.
Lấy phần tử ưu tiên thường tốn , đọc thường tốn O(1). Khi cùng một có chi phí tốt hơn, thuật toán phải cập nhật khóa hoặc xử lý bản ghi cũ phù hợp.
Ví dụ
Các nút có khóa A: 7, B: 3, C: 5. Cấu trúc min lấy B trước.
Khi nào cần dùng?
Hiểu UCS, Dijkstra và A* khi chọn nút có chi phí nhỏ nhất.
Câu hỏi ôn lại
Khóa 2 được thêm sau khóa 9. Min-priority lấy khóa nào trước?
Xem đáp án
2, vì ưu tiên dựa trên giá trị khóa.