我正在开发一个演示 Djikstra算法 的应用程序，并且要使用它，我需要在元素值减小时恢复堆属性。
有关复杂性的问题是， 当算法更改元素的值时， 用于优先级队列的内部结构（在这种情况下为堆）中该 元素的索引 是未知的 。这样，我目前需要执行O（n）搜索以恢复索引，然后才能对其执行实际的 减少键 。
而且，我不确定该操作所需的实际代码。我在这里将D堆用于我的优先级队列。伪代码会有所帮助，但我希望使用Java中的示例来说明如何实现。
您可以执行以下操作：将一个哈希映射存储在您的堆中，该映射将您的堆 值 映射到堆索引。然后，您应该扩展一下通常的堆逻辑：
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，以恢复min- heap-property。
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）：首先，在O（1）的哈希图中查找索引，然后像在Insert / ExtractMin中那样，为O（log（N））恢复堆属性。
重要说明：使用值进行索引查找将要求它们是唯一的。如果您对此条件不满意，则必须在键值对中添加一些唯一ID，并维护此唯一ID与堆索引之间的映射，而不是值索引映射。但是对于Dijkstra则不需要，因为您的值将是图节点，并且您不希望优先级队列中有重复的节点。
