Python - Đống
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ó. Sau đó, nó được gọi là Min Heap. Nếu mỗi nút cha lớn hơn hoặc bằng nút con của nó thì nó được gọi là một đống tối đa. Nó rất hữu ích là triển khai 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. Một cuộc thảo luận chi tiết về đống có sẵn trong trang web của chúng tôi tại đây. Vui lòng nghiên cứu nó trước nếu bạn chưa quen với cấu trúc dữ liệu đầu. Trong chương này, chúng ta sẽ thấy việc triển khai cấu trúc dữ liệu heap bằng cách sử dụng python.
Tạo một đống
Một 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 đến vị trí đầu tiên.
import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)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 đống
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.
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)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 đống
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 loại bỏ phần tử ở vị trí chỉ mục 1.
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)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 đống và chèn phần tử mới vào tại một số vị trí không cố định theo bất kỳ thứ tự nào.
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)[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]