Heap queue (hàng đợi heap) 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 thông qua module heapq. Cấu trúc này rất hữu ích trong việc triển khai hàng đợi ưu tiên (priority queue), nơi phần tử có trọng số cao hơn được ưu tiên xử lý trước.
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 cung cấp 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 chính:
- heapify – 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. Tuy nhiên, các phần tử dữ liệu còn lại không nhất thiết được sắp xếp.
- heappush – Thêm một phần tử vào heap mà không làm thay đổi heap hiện tại.
- heappop – Trả về và loại bỏ phần tử dữ liệu nhỏ nhất từ heap.
- heapreplace – 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ẽ 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ó cho 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ử đó vào 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ỉ khi nó là 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ó cho 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 (phần tử nhỏ nhất).
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ó cho 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 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ó cho kết quả sau:
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]