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

Question

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

关于复杂的问题是,当算法改变的元素的值,该元素的索引用于优先级队列中的内部结构(堆在这种情况下)是未知的.因此,我之前需要进行O(n)搜索,以便恢复索引,然后才能对其执行实际的减少键.

而且,我不确定操作所需的实际代码.我在这里使用D-Heap 作为我的优先级队列.伪代码会有所帮助,但我更喜欢Java中的一个例子,说明应该如何做.

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

在恢复堆属性时,Insert和ExtractMin调用Swap log(N)次.而你正在向Swap添加O(1)开销,因此两个操作都保持为O(log(n)).UpdateKey也是log(N):首先在O(1)的hashmap中查找索引,然后像在Insert/ExtractMin中那样恢复O(log(N))的堆属性.

重要说明:使用索引查找值将要求它们是唯一的.如果您对此条件不满意,则必须向键值对添加一些唯一ID,并维护此唯一ID和堆索引之间的映射,而不是值索引映射.但是对于Dijkstra而言,它不是必需的,因为您的值将是图形节点,并且您不希望优先级队列中有重复的节点.

Answer 2

根据这个问题,没有必要使用减小键方法来实现Dijkstra算法.

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

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

编辑:稍后回答这个问题,我对我的回答感到有点失望:除非你以后做一些特殊的操作,否则所有这些事情都必须从队列中解脱出来.像生活中的许多事情一样,它取决于你如何管理你的记忆以及与此相关的成本.但一般意义仍然是:即使可能需要减少密钥也是不必要的.