如何实现基于最小堆的优先队列中O(logn)的减少关键字操作？

Question

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

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

此外，我并不确定所需操作的实际代码。我在我的优先级队列中使用 D-Heap （点击此处）。虚拟代码会有帮助，但我更喜欢在Java上提供实例以了解如何完成此操作。

- jathanasiou

---

请参见http://en.m.wikipedia.org/wiki/Dijkstra's_algorithm#Running_time。 - Oliver Charlesworth

从上面的链接中可以看到，为了避免在普通二叉堆的减小关键字步骤中进行O（|V|）次查找，有必要维护一个补充索引，将每个顶点映射到堆的索引上（并随着优先队列G的变化而保持其最新状态），这样只需要花费O（log |V|）的时间。 - Brainstorm

@Brainstorm 我确实考虑过使用映射，但我担心它可能会对其他操作产生影响。不过我猜这可能是唯一的解决方法。 - jathanasiou

Answer 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，以恢复最小堆属性。

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

在恢复堆属性时，插入和ExtractMin调用Swap log（N）次。您为Swap添加了O（1）开销，因此两个操作仍然是O（log（n））。UpdateKey也是log（N）：首先，您在哈希映射中查找索引为O（1），然后像在Insert / ExtractMin中一样恢复堆属性的O（log（N））。

重要提示：使用索引查找值将需要它们是唯一的。如果您不满意此条件，则必须向键值对添加某些唯一标识，并维护此唯一标识和堆索引之间的映射，而不是值-索引映射。但对于Dijkstra算法来说，这是不必要的，因为您的值将是图节点，并且您不想在优先级队列中有重复节点。

- ptkvsk

---

你也可以使用一个数组，例如 array[vertex id] = heap index 或 -1 表示不存在。这样做可能会占用更多的内存，但比哈希表更快、更简单（没有调整大小和冲突）。而且内存并不重要，因为你已经必须在一个数组中保存图形，所以这只是为每个顶点添加另一个 int。 - Ciro Santilli OurBigBook.com

@Ciro - 你所描述的是直接访问哈希表，但它的使用要求你的n个元素中的每一个都“哈希”到0和n-1之间的唯一值。如果你的顶点没有“顶点ID”，并且你不能或不想动态添加属性到顶点，你就不能使用普通数组。如果你可以添加这样的属性，那么添加“堆索引”属性会更好。哈希表是这里的通用解决方案，操作的平摊时间为O(1)，不会有任何调整大小。 - Dave

@Dave 为什么不会有任何调整大小？ - Marcus Johansson

@lonelyass 使用哈希表会给 Swap 函数增加 O(log(n)) 的开销，而不是 O(1)，这并不好。 - VinGarcia

Answer 2

根据这个Stack Overflow问题，为了实现Dijkstra算法，不必要有一个减小关键字（decrease-key）的方法。

您可以将项添加到优先级队列中，直到需要为止，并跟踪您已经访问过的节点以除去重复项。当您第一次通过从队列中弹出它来实际访问节点时，您已经找到了该节点的最短路径，并可以忽略优先级队列上所有以后出现的该节点。

优先级队列中有许多额外节点并不是太大的问题，因为它是一个O(log N)结构。(对于1百万个项目，您必须进行大约20次比较，对于10亿个项目，则需30次比较。)

编辑：稍后回答此问题时，我对我的答案感到有些失望：所有那些东西都必须从队列中取出，除非您稍后进行一些特殊操作。像生活中的许多事情一样，问题在于如何管理您的内存以及与此相关的成本。但总体而言，重要的是：即使可能是理想的，也不需要减少关键字。

- Richard

---

稍后回答这个问题，我对自己的回答有点失望：除非你稍后进行一些特殊的操作，否则所有这些东西都必须从队列中删除。 - Richard

我有点惊讶你有点失望。实际使用中，“所有这些事情”不会太多，以至于性能会明显降低。在使用C++ STL时，http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ 上有一篇很好的文章采用了这种方法。 - Erick G. Hagstrom

@Richard 这是一个实际的解决方案。我们在应用程序的许多地方使用它，并维护一个单独的无序集合来跟踪已访问的节点。当考虑到每个插入键都需要减少键的开销和复杂度时，你的解决方案要好得多。 - Chenna V

这种方法仍然具有O(mlogn)的渐进时间复杂度。为什么呢？因为在最坏情况下，我们从堆中弹出m次，并将其推入堆m次。由于堆增长到最大尺寸m，每个操作的复杂度都是O(logm)。因此，总时间为O(mlogm + mlogm) = O(mlogm)。但是，m = O(n ^ 2)（握手引理），因此我们有O(mlog(n ^ 2)) = O(mlogn) 时间。对于大型图形，降低关键性能的差异很小。实际上，实现减少关键字所增加的困难是否值得任何非渐近时间效益还存在争议。然而，空间从O(m)减少到O(n)。 - James Lawson

@JamesLawson 在另一个回答中提到：在实践中不使用 DECREASE-KEY 可能更快。https://dev59.com/OWox5IYBdhLWcg3wWzJ7#18540646 - qwr

Answer 3

如果您正在使用C++ STL的make_heap()/pop_heap()/push_heap()，那么没有办法从节点ID保留索引到底层堆向量中的索引，我认为您应该实现自己的堆函数以实现在Increase-Key/Decrease-key操作中的O(logn)。

- zach

---

好的，但是可以通过重新插入而不是减少更改的键来使用STL。http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ - Erick G. Hagstrom

Answer 4

我已经实现了同样的东西。在MinHeap类中，我添加了一个字典，用于以O(1)的时间访问项目。并且在减少键时，它将在O(logn)时间内上升。

class MinHeap:
def __init__(self, array):
    self.heap = self.buildHeap(array)
    self.idx_of_element = {}

def getParentIdx(self, idx):
    return (idx - 1) // 2

def getLeftChildIdx(self, idx):
    return idx * 2 + 1

def getRightChildIdx(self, idx):
    return idx * 2 + 2

def buildHeap(self, array):
    # Write your code here.
    lastIdx = len(array) - 1
    startFrom = self.getParentIdx(lastIdx)
    for i in range(startFrom, -1, -1):
        self.siftDown(i, array)
    return array

# this is min-heapify method
def siftDown(self, idx, array):
    while True:
        l = self.getLeftChildIdx(idx)
        r = self.getRightChildIdx(idx)

        smallest = idx
        if l < len(array) and array[l] < array[idx]:
            smallest = l
        if r < len(array) and array[r] < array[smallest]:
            smallest = r

        if smallest != idx:
            array[idx], array[smallest] = array[smallest], array[idx]
            self.idx_of_element[self.heap[idx]], self.idx_of_element[self.heap[smallest]] = self.idx_of_element[self.heap[smallest]], self.idx_of_element[self.heap[idx]]
            idx = smallest
        else:
            break

- Raj