Python: xóa phần tử khỏi heap

Question

Python có heapq mô-đun thực hiện cấu trúc dữ liệu heap và nó hỗ trợ một số thao tác cơ bản (push, pop).

Làm thế nào để loại bỏ phần tử thứ i từ heap trong O (log n)? Thậm chí có thể với heapq hoặc tôi có phải sử dụng một mô-đun khác không?

Lưu ý, có một ví dụ ở cuối tài liệu: http://docs.python.org/library/heapq.html đề xuất một cách tiếp cận có thể - đây không phải là điều tôi muốn. Tôi muốn phần tử cần xóa, không chỉ đánh dấu là đã xóa.

Answer 1

Bạn có thể loại bỏ các yếu tố thứ i từ một đống khá dễ dàng:

h[i] = h[-1] 
h.pop() 
heapq.heapify(h) 

Chỉ cần thay thế các yếu tố bạn muốn loại bỏ với các yếu tố cuối cùng và loại bỏ các yếu tố cuối cùng sau đó tái heapify đống. Đây là O (n), nếu bạn muốn bạn có thể làm điều tương tự trong O (log (n)) nhưng bạn sẽ cần phải gọi một vài hàm heapify nội bộ, hoặc tốt hơn như larsmans chỉ ra chỉ sao chép nguồn gốc của _siftup/_siftdown ra khỏi heapq.py vào mã của riêng bạn:

h[i] = h[-1] 
h.pop() 
if i < len(h): 
    heapq._siftup(h, i) 
    heapq._siftdown(h, 0, i) 

Lưu ý rằng trong mỗi trường hợp bạn không thể chỉ làm h[i] = h.pop() vì đó sẽ thất bại nếu i tài liệu tham khảo yếu tố cuối cùng. Nếu trường hợp đặc biệt của bạn loại bỏ phần tử cuối cùng thì bạn có thể kết hợp ghi đè và bật lên.

Lưu ý rằng tùy thuộc vào kích thước điển hình của đống của bạn, bạn có thể thấy rằng chỉ gọi heapify trong khi về mặt lý thuyết kém hiệu quả có thể là nhanh hơn so với tái sử dụng _siftup/_siftdown: một chút mẫn sẽ tiết lộ rằng heapify có lẽ thực hiện trong C nhưng việc triển khai C của các hàm bên trong không được hiển thị. Nếu hiệu suất quan trọng với bạn thì hãy xem xét thực hiện một số thử nghiệm tính thời gian trên dữ liệu điển hình để xem dữ liệu nào là tốt nhất. Trừ khi bạn có heaps lớn thực sự lớn-O có thể không phải là yếu tố quan trọng nhất.

Edit: một ai đó cố gắng để chỉnh sửa câu trả lời này để loại bỏ các cuộc gọi đến _siftdown với một lời nhận xét rằng:

_siftdown là không cần thiết. Mới h [i] được đảm bảo là con nhỏ nhất của con cái cũ, mà vẫn còn lớn hơn con của cha mẹ cũ [i] (bố mẹ mới của h [i]). _siftdown sẽ là no-op. Tôi phải chỉnh sửa vì tôi không có đủ đại diện để thêm nhận xét.

Điều họ đã bỏ lỡ trong nhận xét này là h[-1] có thể không phải là con của h[i]. Giá trị mới được chèn vào tại h[i] có thể đến từ một nhánh hoàn toàn khác của heap để nó có thể cần phải được chọn lọc theo một trong hai hướng.

Ngoài ra để nhận xét hỏi tại sao không sử dụng sort() để khôi phục heap: gọi _siftup và _siftdown là cả hai hoạt động O (log n), gọi heapify là O (n).Gọi sort() là một hoạt động O (n log n). Nó là khá có thể là sắp xếp cuộc gọi sẽ được đủ nhanh nhưng đối với đống lớn nó là một chi phí không cần thiết.

Đã chỉnh sửa để tránh sự cố được chỉ ra bởi @Seth Bruder. Khi i tham chiếu đến phần tử kết thúc, lệnh gọi _siftup() sẽ không thành công, nhưng trong trường hợp đó, việc nảy sinh một phần tử ở cuối vùng heap không phá vỡ sự bất biến của đống.

Answer 2

(a) Xem xét lý do bạn không muốn xóa lười. Đó là giải pháp đúng trong nhiều trường hợp.

(b) Heap là danh sách. Bạn có thể xóa một phần tử theo chỉ mục, giống như bất kỳ danh sách nào khác, nhưng sau đó bạn sẽ cần phải khôi phục lại nó, bởi vì nó sẽ không còn thỏa mãn bất biến heap nữa.