Heap queue là một cấu trúc cây đặc biệt trong đó mỗi nút cha đều nhỏ hơn hoặc bằng các nút con của nó. Trong Python, nó được triển khai bằng module heapq. Nó rất hữu ích trong việc triển khai hàng đợi ưu tiên (priority queue) nơi mục hàng đợi có trọng số cao hơn được ưu tiên xử lý.
Tạo một Heap
Một heap queue được tạo bằng cách sử dụng thư viện tích hợp sẵn của Python tên là heapq. Thư viện này có các hàm liên quan để thực hiện nhiều thao tác trên cấu trúc dữ liệu heap. Dưới đây là danh sách các hàm này.
- heapify – Hàm này chuyển đổi một danh sách thông thường thành heap. Trong heap kết quả, phần tử nhỏ nhất được đẩy về vị trí chỉ số 0. Nhưng các phần tử dữ liệu còn lại không nhất thiết được sắp xếp.
- heappush – Hàm này thêm một phần tử vào heap mà không làm thay đổi heap hiện tại.
- heappop – Hàm này trả về phần tử dữ liệu nhỏ nhất từ heap.
- heapreplace – Hàm này thay thế phần tử dữ liệu nhỏ nhất bằng một giá trị mới được cung cấp trong hàm.
Tạo Heap
Một heap được tạo đơn giản bằng cách sử dụng một danh sách các phần tử với hàm heapify. Trong ví dụ dưới đây, chúng ta cung cấp một danh sách các phần tử và hàm heapify sắp xếp lại các phần tử, đưa phần tử nhỏ nhất về vị trí đầu tiên.
Ví dụ
import heapq H = [21, 1, 45, 78, 3, 5] # Sử dụng heapify để sắp xếp lại các phần tử heapq.heapify(H) print(H)
Kết quả
Khi mã trên được thực thi, nó tạo ra kết quả sau:
[1, 3, 5, 78, 21, 45]
Chèn vào Heap
Việc chèn một phần tử dữ liệu vào heap luôn thêm phần tử ở chỉ số cuối cùng. Nhưng bạn có thể áp dụng lại hàm heapify để đưa phần tử mới thêm về chỉ số đầu tiên chỉ nếu nó nhỏ nhất về giá trị. Trong ví dụ dưới đây, chúng ta chèn số 8.
Ví dụ
import heapq H = [21, 1, 45, 78, 3, 5] # Chuyển đổi thành heap heapq.heapify(H) print(H) # Thêm phần tử heapq.heappush(H, 8) print(H)
Kết quả
Khi mã trên được thực thi, nó tạo ra kết quả sau:
[1, 3, 5, 78, 21, 45] [1, 3, 5, 78, 21, 45, 8]
Xóa khỏi Heap
Bạn có thể xóa phần tử ở chỉ số đầu tiên bằng hàm này. Trong ví dụ dưới đây, hàm sẽ luôn xóa phần tử ở vị trí chỉ số 0.
Ví dụ
import heapq H = [21, 1, 45, 78, 3, 5] # Tạo heap heapq.heapify(H) print(H) # Xóa phần tử khỏi heap heapq.heappop(H) print(H)
Kết quả
Khi mã trên được thực thi, nó tạo ra kết quả sau:
[1, 3, 5, 78, 21, 45] [3, 21, 5, 78, 45]
Thay thế trong Heap
Hàm heapreplace luôn xóa phần tử nhỏ nhất của heap và chèn phần tử mới đến vào vị trí nào đó không cố định theo thứ tự nào.
Ví dụ
import heapq H = [21, 1, 45, 78, 3, 5] # Tạo heap heapq.heapify(H) print(H) # Thay thế một phần tử heapq.heapreplace(H, 6) print(H)
Kết quả
Khi mã trên được thực thi, nó tạo ra kết quả sau:
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]