Hàng đợi Heap là một cấu trúc cây đặc biệt, trong đó mỗi nút cha nhỏ hơn hoặc bằng nút con của nó. Trong pythin, nó được thực hiện bằng cách sử dụng mô-đun heapq. Nó rất hữu ích là triển khai các hàng đợi ưu tiên trong đó mục hàng đợi có trọng số cao hơn được ưu tiên xử lý nhiều hơn.
Tạo một đống
Hàng đợi heap được tạo bằng cách sử dụng thư viện có sẵn của python có tên là heapq. Thư viện này có các chức năng liên quan để thực hiện các hoạt động khác nhau trên cấu trúc dữ liệu heap. Dưới đây là danh sách các chức năng này.
- heapify - Hàm này chuyển đổi một danh sách thông thường thành một heap. Trong đống kết quả, phần tử nhỏ nhất được đẩy lên vị trí chỉ mục 0. Nhưng phần còn lại của các phần tử dữ liệu không nhất thiết phải được sắp xếp.
- Heappush - Chức năng 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 một đống
Một heap được tạo bằng cách đơn giản sử dụng danh sách các phần tử có chức năng heapify. Trong ví dụ dưới đây, chúng tôi cung cấp 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 lên vị trí đầu tiên.
Ví dụ
import heapq H = [21,1,45,78,3,5] # Use heapify to rearrange the elements heapq.heapify(H) print(H)
Đầu ra
Khi đoạn 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
Chèn một phần tử dữ liệu vào một heap luôn thêm phần tử vào chỉ mục cuối cùng. Nhưng bạn có thể áp dụng lại hàm heapify để đưa phần tử mới được thêm vào chỉ mục đầu tiên chỉ khi nó có giá trị nhỏ nhất. Trong ví dụ dưới đây, chúng tôi chèn số 8.
Ví dụ
import heapq H = [21,1,45,78,3,5] # Covert to a heap heapq.heapify(H) print(H) # Add element heapq.heappush(H,8) print(H)
Đầu ra
Khi đoạn 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]
Đang xóa khỏi heap
Bạn có thể xóa phần tử lúc đầu chỉ mục bằng cách sử dụng chức năng này. Trong ví dụ dưới đây, hàm sẽ luôn xóa phần tử ở vị trí chỉ mục 1.
Ví dụ
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Remove element from the heap heapq.heappop(H) print(H)
Đầu ra
Khi đoạn 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 một đống
Hàm heapreplace luôn loại bỏ phần tử nhỏ nhất của vùng đống và chèn phần tử mới đến ở một số vị trí không cố định theo bất kỳ thứ tự nào.
Ví dụ
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Replace an element heapq.heapreplace(H,6) print(H)
Đầu ra
Khi đoạn 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]