60

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.

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.

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.

4

4 回答 4

43

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

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) 次。而且您正在向 Swap 添加 O(1) 开销，因此这两个操作仍然是 O(log(n))。UpdateKey 也是 log(N)：首先在哈希图中查找 O(1) 的索引，然后像在 Insert/ExtractMin 中一样恢复 O(log(N)) 的堆属性。

重要提示：使用索引查找的值将要求它们是唯一的。如果您不同意这种情况，则必须向键值对添加一些唯一 id，并维护此唯一 id 和堆索引之间的映射，而不是值索引映射。但对于 Dijkstra 来说，它不是必需的，因为您的值将是图形节点，并且您不希望优先级队列中有重复的节点。

于 2013-07-10T21:36:18.073 回答
23

根据这个 SO question，为了实现 Dijkstra 算法，没有必要使用减少键方法。

您可以根据需要多次将项目添加到优先级队列中，并跟踪您访问过的节点以清除重复项。第一次通过将节点从队列中弹出来实际访问它时，您已经找到了到该节点的最短路径，并且可以忽略它在优先级队列中的所有未来出现。

在优先级队列上有许多额外的节点并不是什么大问题，因为它是一个O(log N)结构。（您必须对 100 万个项目进行大约 20 次比较，对 10 亿个项目进行 30 次比较。）

编辑：稍后跟进这个问题，我对我的回答有点失望：除非你稍后做一些特殊的处理，否则所有这些事情都必须退出队列。就像生活中的许多事情一样，它归结为你如何管理你的记忆以及与此相关的成本。但一般的观点仍然存在：减少键不是必需的，即使它可能是可取的。

于 2015-06-29T18:39:24.540 回答
0

如果您使用的是c ++ stl make_heap()/pop_heap()/push_heap()，则无法在下划线堆向量中保留从节点id到索引的索引，我认为您应该实现自己的堆函数来实现O( logn) 在递增键/递减键操作中。

于 2015-10-07T03:17:17.507 回答
0

我实施了同样的事情。在 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
于 2019-09-17T20:38:57.263 回答