h = []
heapq.heappush(h,(10, 1200))
heapq.heappush(h,(20, 31))
heapq.heappush(h,(5, 1))
Tôi muốn duy trì kích thước cố định là 3, vì vậy khi tôi tiếp theo có heapq.heappush(h,(3,15)), khóa có giá trị 20 bị xóa và tôi còn lại với giá trị 3,5 và 10. Có ý tưởng nào không?Duy trì kích thước cố định heap-python
Không có tích hợp sẵn trong heapq để kiểm tra kích cỡ, vì vậy bạn sẽ cần phải làm điều đó bản thân:
if len(h) < capacity:
heapq.heappush(h, thing)
else:
# Equivalent to a push, then a pop, but faster
spilled_value = heapq.heappushpop(h, thing)
do_whatever_with(spilled_value)
Ngoài ra, lưu ý heapq mà thực hiện một đống phút, không phải là một đống max. Bạn sẽ cần phải đảo ngược thứ tự ưu tiên của bạn, có thể bằng cách phủ nhận chúng.
Các hoạt động pop trong heappushpop trả về mục nhỏ nhất nhưng tôi cần phải bật mục tối đa khi xem xét min heap. – user2991421
@ user2991421: Bạn có cần cả hai loại bỏ-phút và loại bỏ-max? Nếu bạn cần cả hai, một đống không phải là công cụ cho công việc. Nếu bạn chỉ cần loại bỏ-tối đa, đảo ngược các ưu tiên sẽ có hiệu quả cung cấp cho bạn một heap tối đa. – user2357112
Những gì tôi cần được đưa ra một heap min hoặc heap tối đa loại bỏ các yếu tố tối đa từ min heap hoặc loại bỏ các yếu tố min từ heap tối đa để khi tôi thêm một phần tử mới tôi đã cố định kích thước đống. – user2991421
Đây có phải là một vùng tối đa hoặc một đống tối thiểu không? Nếu đó là một đống heap, bạn sẽ gặp vấn đề, vì bạn cần một thao tác remove-max cho việc này. – user2357112
Tôi muốn một heap tối đa. Sau đó, bạn có nếu có bất kỳ chức năng min loại bỏ được xác định trước. – user2991421
remove-min là 'heapq.heappop'. – user2357112