Trong cuộc thảo luận về cấu trúc dữ liệu heap, ví dụ: CLRS, hàng đợi ưu tiên tối đa chỉ cần INSERT, MAXIMUM, EXTRACT-MAX và INCREASE-KEY. Nhưng tại sao nó cũng không có DECREASE-KEY, ít nhất, hoạt động của nó cũng sẽ làm mất hiệu lực tài sản heap? Có thực tế không quan trọng?Tại sao hàng đợi không có mức ưu tiên tối đa có DECREASE-KEY?
FWIW CLR V1 của tôi nói về INSERT, MIN, EXTRACT-MIN, UNION, DECREASE-KEY và DELETE, nhưng chúng tôi có thể chuyển đổi sang phiên bản của bạn bằng cách lật các biển báo.
Tôi nghĩ rằng tập hợp này được thúc đẩy bởi các yêu cầu của thuật toán sử dụng hàng đợi ưu tiên, chẳng hạn như cây bao trùm tối thiểu, đường đi ngắn nhất Dijstra và (Tôi nghi ngờ) A *. Ví dụ, nếu bạn nhìn vào phần đầu của chương về cây bao trùm tối thiểu, bạn có thể thấy một lưu ý rằng thuật toán của Prim có thể được tăng tốc nếu bạn thay thế đống nhị phân bằng đống heaps.
"CLR V1 của tôi"? Bạn có thể giải thích được không? Chính xác, những gì tôi đã yêu cầu thực sự tương ứng với "Tại sao hàng đợi ưu tiên tối thiểu có TĂNG-KEY?" –
"CLR v1 của tôi" đề cập đến ấn bản đầu tiên của cuốn sách, mà không có Stein làm tác giả. Đoạn thứ hai trả lời câu hỏi của bạn, mặc dù: các thuật toán sử dụng hàng đợi ưu tiên chỉ cần có khả năng di chuyển các mục nhập trước đó trong hàng đợi, không muộn hơn. – Novelocrat
Không có gì ngăn bạn thực hiện DECREASE-KEY trong heap nhị phân của bạn. Nó có thể được thực hiện trong O (log N) mà không vi phạm bất kỳ bất biến nào.
Tôi đoán là nó không được bao gồm, bởi vì nó không cần thiết rất thường xuyên.
Mã giả của bạn để thực hiện điều này là gì? Chỉ cần heapify tại vị trí hiện tại? –
Giả sử "heapify" có nghĩa là di chuyển nút hiện tại xuống cho đến khi các bất biến heap được thỏa mãn, sau đó vâng. – svick
Nếu bạn có MAX-HEAP, DECREASE-KEY sẽ là MAX-HEAPIFY trong phần 6.2 "Duy trì thuộc tính đống" của CLRS, ấn bản thứ ba.
Tôi nghĩ rằng điều này liên quan đến cách hàng đợi ưu tiên tối thiểu thường không có INCREASE-KEY, mặc dù nó là một hoạt động hoàn toàn được xác định rõ ràng. Tôi đoán là đây chỉ là thứ không phát sinh nhiều. Ngoài ra, w00t ngày nhận được chính xác 1337 danh tiếng! – templatetypedef
Tôi có thể thề rằng tôi đã hỏi câu hỏi chính xác này trước đây nhưng tôi không thể tìm thấy nó. –
https://cs.stackexchange.com/questions/10203/increase-key-and-decrease-key-in-a-binary-min-heap – max