HEAP-INCREASE-KEY複雜度

Question

讓A成爲一個堆，它不是以常規方式存儲值，而只是定期存儲根，並且每個子存儲爲它與其父項之間的差異。 HEAP-INCREASE-KEY（A，i，key）操作的複雜性是什麼（操作更新節點上的節點的key到key）？

Answer 1

它可以在O(log N)時間像在一個正常的堆中完成。要找到存儲在節點i中的新值，可以遍歷從堆根目錄到此節點的路徑，以便根據它與其父節點之間的差異表示新的key值。之後，篩選程序可以以與在普通堆中完成的方式幾乎相同的方式執行。在進行篩選程序交換時，這些值只會改變這兩個交換節點及其子元素。因此，一次交換需要更新O(1)。這就是爲什麼總時間複雜度爲O(log N)。

這是實現它的一種簡單方法：
1.如果節點位於堆根和更新節點之間的路徑上，我們稱它爲「已觸及」節點。如果節點與最接近的「已觸摸」節點之間的距離至多爲2，我們稱節點爲「重建」。
2.對於每個「重建」節點，可以通過遍歷堆來計算其真值。請注意，對於任何查詢，都有O(log N)「重建」節點。
3.重建所有「重建」節點的真值後，可以運行一個通常的篩選程序。
4.在此過程完成後，可以通過遍歷所有「重建」節點的堆來計算節點與其父節點之間的差異。所有其他節點都不會被觸摸。