如何为基于最小堆的优先级队列实现O（logn）减少键操作？ [英] How to implement O(logn) decrease-key operation for min-heap based Priority Queue?

问题描述

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

I am working on an application that demonstrates the Djikstra's algorithm, and to use it, I need to restore the heap property when my elements' value is decreased.

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

The problem regarding the complexity is that when the algorithm changes the value of an element, that element's index in the internal structure (heap in this case) used for the priority queue is unknown. As such, I currently need to do an O(n) search, in order to recover the index, before I can perform an actual decrease-key on it.

此外，我不确定该操作所需的实际代码。我在此处使用了我的优先级队列。伪代码会有所帮助，但是我希望在Java中使用一个示例说明如何完成此操作。

Moreover, I am not exactly sure about the actual code needed for the operation. I am using the D-Heap here for my Priority Queue. Pseudocode would help, but I would prefer an example in Java on how this should be done.

推荐答案

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

You can do following: store a hashmap inside your heap that maps your heap values to heap indexes. Then you should extend your usual heap-logic just a bit:

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） code> DecreaseKey 和 BubbleDown / Heapify（index）（如果 IncreaseKey ，以还原最小堆属性。

BubbleUp(index) in case of DecreaseKey, and BubbleDown/Heapify(index) in case of IncreaseKey, to restore min-heap-property.

这是我的C＃实现： http：// pastebin.com/kkZn123m

恢复堆属性时，Insert和ExtractMin调用Swap log（N）次。而且您要在交换中增加O（1）的开销，因此两个操作都保持为O（log（n））。 UpdateKey也是log（N）：首先，在O（1）的哈希图中查找索引，然后像在Insert / ExtractMin中那样为O（log（N））恢复堆属性。

Insert and ExtractMin call Swap log(N) times, when restoring heap property. And you're adding O(1) overhead to Swap, so both operations remain O(log(n)). UpdateKey is also log(N): first you lookup index in a hashmap for O(1), then you're restoring heap property for O(log(N)) as you do in Insert/ExtractMin.

重要说明：使用值进行索引查找将要求它们是唯一的。如果您不满意这种情况，则必须在键值对中添加一些唯一ID，并保持此唯一ID与堆索引之间的映射，而不是值索引映射。但是对于Dijkstra而言，则不需要，因为您的值将是图形节点，并且您不希望优先级队列中有重复的节点。

Important note: using values for index lookup will require that they are UNIQUE. If you're not ok with this condition, you will have to add some uniqueue id to your key-value pairs and maintain mapping between this uniqueue id and heap index instead of value-index mapping. But for Dijkstra it's not needed, as your values will be graph nodes and you don't want duplicate nodes in your priority queue.

这篇关于如何为基于最小堆的优先级队列实现O（logn）减少键操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！