如何实现基于最小堆的优先级队列的O(logn)减less键操作?

我正在开发一个演示Djikstraalgorithm的应用程序,为了使用它,我需要在元素值减less时恢复堆属性。

关于复杂性的问题是, 当algorithm改变元素的值时,用于优先级队列的内部结构(在这种情况下为堆)中的该元素的索引 是未知的 。 因此,我现在需要做一个O(n)的search,以便恢复索引,然后才能对其执行实际的减键

而且,我并不完全确定操作所需的实际代码。 我在这里使用D堆作为我的优先级队列。 伪代码将有所帮助,但我更喜欢Java中的一个例子,如何做到这一点。

您可以执行以下操作:在您的堆中存储将您的堆映射到堆索引的hashmap。 那么你应该延长你平时的堆逻辑:

on Swap(i, j): map[value[i]] = j; map[value[j]] = i; 

 on Insert(key, value): map.Add(value, heapSize) in the beginning; 

 on ExtractMin: map.Remove(extractedValue) in the end; 

 on UpdateKey(value, newKey): index = map[value]; keys[index] = newKey; 

BubbleDown/Heapify(index)情况下为BubbleUp(index)BubbleDown/Heapify(index)情况下为BubbleDown/Heapify(index) ,以恢复min-heap-property。

这是我的C#实现: http : //pastebin.com/kkZn123m

插入和ExtractMin调用在恢复堆属性时交换日志(N)次。 而且你将O(1)开销join到Swap中,所以两个操作都保持为O(log(n))。 UpdateKey也是log(N):首先在O(1)的hashmap中查找索引,然后像在Insert / ExtractMin中那样为O(log(N))恢复heap属性。

重要提示:使用索引查找的值将需要它们是唯一的。 如果你不满足这个条件,你将不得不添加一些独特的id到你的键值对,并维护这个uniqueue id和堆索引之间的映射,而不是值索引映射。 但是对于Dijkstra来说这不是必须的,因为你的值是图节点,你不希望在你的优先级队列中有重复的节点。

根据这个问题 ,为了实现Dijkstra的algorithm,没有必要使用递减关键字方法。

您可以根据需要简单地将项目添加到优先级队列中,并跟踪您访问过哪些节点以清除重复项。 第一次通过将其从队列中popup来实际访问某个节点时,find了该节点的最短path,并且可以在优先级队列上忽略将来出现的所有节点。

在优先级队列上有许多额外的节点不是什么大问题,因为它是O(log N)结构。 (你必须做100个项目的20个比较和10个项目的30个比较。)

编辑:稍后跟进这个问题,我对我的回答有点失望:除非你稍后做一些特殊的推理,否则所有这些事情都必须排队。 像生活中的许多事情一样,这取决于如何pipe理自己的记忆和与此相关的成本。 但总体观点仍然是:减键不是必要的 ,即使它可能是可取的。

如果你正在使用c ++ stl make_heap()/ pop_heap()/ push_heap(),那么在下划线堆向量中没有办法保留从节点id到索引的索引,我想你应该实现你自己的堆函数来实现Ologin)在增加键/减less键操作。

    Interesting Posts