Hoạt động xóa-tối đa trong một heap tối thiểu

Question

Tôi đang triển khai một vùng tối thiểu tối đa, một loại hàng đợi ưu tiên kép. Bạn có thể xem tại đây here để biết thêm thông tin về heaps tối đa.

Mã để chèn và thao tác xóa-min rất đơn giản và có sẵn trên mạng. Tuy nhiên, tôi cũng đang cố gắng triển khai hoạt động xóa-tối đa trên heap tối thiểu. Ban đầu, tôi cảm thấy rằng xóa-max trong min-max heap sẽ giống như xóa-max trong đống tối đa (nếu chúng ta xem xét subtree của min-max heap chứa phần tử tối đa, nó giống như một max- min heap). Vì vậy, việc thực hiện sẽ đơn giản và tương tự như xóa-min của min-max heap.

Nhưng, có một vấn đề:

Như có thể thấy trong hình trên, mặc dù 70 là yếu tố tối đa, yếu tố cuối cùng (12) của heap min-max được không cây con có chứa 70. Vì vậy, tôi có thể sử dụng nó để thay thế khoảng trống còn lại trong cây con trái sau khi xóa 70?

Nếu chúng tôi không sử dụng phần tử đó và thay vào đó hãy làm theo quy trình xóa tối đa của vùng tối đa và sử dụng 20 để thay thế khoảng cách, phần tử tiếp theo được chèn vào heap sẽ ở đúng con 10 và mãi mãi sẽ không có con đúng nào của số 9.

Vì vậy, bất kỳ ai cũng có thể giúp tôi không?

Answer 1

Tôi tin rằng việc xóa nút ngoài cùng bên phải ở mức cuối cùng là chính xác và sử dụng nó để thay thế phần tử tối đa đã bị xóa, ngay cả khi nó vượt qua trên cây. Lý do là như sau:

1. Loại bỏ các nút ngoài cùng bên phải ở mức cuối cùng không thay đổi bất kỳ bất biến mà cần phải giữ cho bất kỳ nút trong cây rằng: tất cả các nút ở mức tối thiểu vẫn còn nhỏ hơn tất cả các hậu duệ của họ, và tất cả các nút ở mức tối đa vẫn lớn hơn con cháu của họ.

2. Cây vẫn là cây nhị phân hoàn chỉnh.

Khi bạn đã di chuyển nút này qua, bạn có thể sử dụng thủ tục sửa lỗi bình thường trong vùng tối đa để đảm bảo rằng các biến thể subtree trái vẫn giữ.

Hy vọng điều này sẽ hữu ích!