我正在开发一个演示 Djikstra 算法 的应用程序，要使用它，我需要在我的元素值减少时恢复堆属性。
关于复杂性的问题是当算法改变一个元素的值时，该元素的索引在用于优先级队列的内部结构(在本例中为堆)中是未知的。因此，我目前需要进行复杂度为 O(n) 的搜索，以便恢复索引，然后才能对其执行实际的减少键。
此外，我不确定操作所需的实际代码。我正在使用 D-Heap here对于我的优先队列。伪代码会有所帮助，但我更喜欢 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;
BubbleUp(index) 在 DecreaseKey 的情况下，BubbleDown/Heapify(index) 在 IncreaseKey 的情况下>，恢复最小堆属性。
这是我的 C# 实现:http://pastebin.com/kkZn123m
恢复堆属性时，Insert 和 ExtractMin 调用 Swap log(N) 次。并且您将 O(1) 开销添加到 Swap，因此这两个操作仍然是 O(log(n))。 UpdateKey 也是 log(N):首先您在 HashMap 中查找 O(1) 的索引，然后像在 Insert/ExtractMin 中一样恢复 O(log(N)) 的堆属性。
重要说明:使用值进行索引查找将要求它们是唯一的。如果您对这种情况不满意，则必须向键值对添加一些唯一 ID，并维护此唯一 ID 和堆索引之间的映射，而不是值索引映射。但对于 Dijkstra 来说不需要，因为您的值将是图形节点，并且您不希望优先级队列中有重复的节点。
关于algorithm - 如何为基于最小堆的优先级队列实现 O(logn) 减键操作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17009056/