如何为基于最小堆的优先级队列实现O（logn）减少键操作？

小编典典

如何为基于最小堆的优先级队列实现O（logn）减少键操作？

algorithm

我正在开发一个演示 Djikstra算法 的应用程序，并且要使用它，我需要在元素值减小时恢复堆属性。

有关复杂性的问题是， 当算法更改元素的值时， 用于优先级队列的内部结构（在这种情况下为堆）中该 元素的索引 是未知的
。这样，我目前需要执行O（n）搜索以恢复索引，然后才能对其执行实际的 减少键 。

而且，我不确定该操作所需的实际代码。我在这里将D堆用于我的优先级队列。伪代码会有所帮助，但我希望使用Java中的示例来说明如何实现。

阅读 250

2020-07-28

共1个答案

小编典典

您可以执行以下操作：将一个哈希映射存储在您的堆中，该映射将您的堆值映射到堆索引。然后，您应该扩展一下通常的堆逻辑：

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。

这是我的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则不需要，因为您的值将是图节点，并且您不希望优先级队列中有重复的节点。

2020-07-28