在O（log（n））複雜性中更改二進制堆元素的優先級

Question

我寫了一個存儲優先級類（私有成員爲PRIORITY和KEY）的二進制堆。我想知道當我給出變量的KEY時，如何在小於O（n）複雜度的情況下改變堆中元素的優先級。在此先感謝

Answer 1

解決此問題的一種方法是有另一種結構（我將調用該輔助數據結構）。例如將密鑰映射到二進制堆中的元素的散列映射（例如unordered_map）。您可以使用此數據結構來查找堆中的哪個元素需要修改其優先級。修改元素的優先級後，需要對其執行一個sink和一個sift操作。這兩種操作都具有複雜性O(log(n))因此總體上對優先級的修改具有複雜性O(log(n))。在這裏我假設你使用一個輔助數據結構，它支持通過複雜度不超過O(log(n))（在散列映射的複雜度爲O（1））的情況下通過密鑰查找。

請注意，您必須修改已經爲二進制堆實施的操作，以使輔助數據結構與二進制堆保持同步。