從堆中刪除第i個節點

Question

我知道從堆中刪除節點是發生在根上的O(log n)。而且我也知道在堆樹問題之一中刪除一個堆中的任意節點並且是O(n)。

是否有減少從maxheap刪除Ith的節點O(log n)其中我是從1至N的運行時間的任何算法？

Answer 1

從堆刪除的任意的節點的昂貴的部分不處於刪除，但在發現刪除的節點。實際上刪除節點是O（log n）。但首先，您必須對底層數據存儲進行順序掃描才能找到節點。這是O（n）部分。

加快這唯一的辦法是保持第二數據結構就像一本字典或哈希映射或類似，能夠迅速告訴你，該項目是在後備存儲。然後，您在字典中進行O（1）查找，從字典中刪除O（1），並從堆中刪除O（log n）。