如何实现基于最小堆的优先级队列的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键操作。
