如何为基于最小堆的优先级队列实现O（logn-key）减少操作？
我正在开发一个演示Djikstra算法的应用程序，要使用它，我需要在元素的值减少时恢复堆属性。
关于复杂性的问题是，当算法改变一个元素的值时，该元素在用于优先级队列的内部结构（在本例中为堆）中的索引是未知的。因此，我目前需要进行O（n）搜索，以便恢复索引，然后才能对其执行实际的减键。
此外，我不能完全确定操作所需的实际代码。我在这里使用D堆作为优先级队列。伪代码会有所帮助，但我更喜欢Java中的一个例子，说明应该如何做到这一点。
共有3个答案
如果你使用的是c stlmake_heap（）/pop_heap（）/push_heap（），没有办法在下划线堆向量中保持从节点id到索引的索引，我认为你应该实现自己的堆函数来实现增加键/减少键操作中的O（logn）。
根据这个SO问题，没有必要使用减键方法来实现Dijkstra算法。
您只需将一个项目添加到优先级队列中，并根据需要多次跟踪您访问过的节点，以清除重复项。第一次从队列中弹出一个节点来实际访问该节点时，您已经找到了该节点的最短路径，并且可以忽略该节点将来在优先级队列中出现的所有情况。
在优先级队列上有许多额外的节点并不是什么大问题，因为它是一种O（log N）结构。（你需要对100万个项目进行20次比较，对10亿个项目进行30次比较。）
编辑：稍后继续这个问题，我对我的回答有点失望：除非你以后做一些特殊的调整，否则所有这些事情都必须从队列中删除。像生活中的许多事情一样，这归结为你如何管理你的记忆以及这样做的相关成本。但总的一点仍然是：减少键是不必要的，即使它可能是可取的。
可以执行以下操作：在堆内存储一个hashmap，将堆值映射到堆索引。然后，您应该稍微扩展一下通常的堆逻辑：
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
还原堆属性时，插入和提取最小调用交换日志（N）次。您将O（1）开销添加到交换中，因此两个操作都保持O（log（n））。UpdateKey也是log（N）：首先在hashmap中查找O（1）的索引，然后像在Insert/ExtractMin中一样恢复O（log（N））的堆属性。
重要提示：使用值进行索引查找需要它们是唯一的。如果您不同意这种情况，您将不得不在键值对中添加一些统一队列ID，并保持这个统一队列ID和堆索引之间的映射，而不是值索引映射。但是对于Dijkstra来说，这是不需要的，因为您的值将是图节点，并且您不希望优先级队列中有重复的节点。
-
我目前正在尝试实现min heap PQ，但是我在实现的正确性方面遇到了一些问题，我似乎无法找出我做错了什么——它没有输出最低优先级，也没有对它们进行正确排序。 使用以下测试数据： 我得到以下结果： 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子，但最后一个输出是最大的优先级，所以这没有意义。我花了几个小时试图研究堆优先级队列，但我找不到任何帮助。 以下是CMP要求的更好的代码
-
我正在编写一个涉及堆实现的代码，在我的bubbleUp方法中，在我的while循环行中，我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题，但解决这个问题的最佳方法是什么？我在实现removeHigh方法时也遇到了一些问题，该方法旨在从队列中移除最高的元素。
-
1）insert（name,priority）：这个函数应该取一个string类型的名称和一个integer类型的优先级，并将它们插入到优先级队列中。remove（）：这个函数应该移除具有最高优先级值的对象，并从对象中返回名称字符串。 2）作为背景，我有三个类用于这个程序：第一，包含读取文件和使用函数的实现的“main”类。第二，“name”类，它创建包含名称字符串和优先级int的name对象、一
-
我在CLRS，第三版（第662页）中读到了Dijkstra的算法。下面是我不明白的书中的一部分： 如果图足够稀疏--特别是-我们可以通过用二进制最小堆实现最小优先级队列来改进算法。 为什么图形应该是稀疏的？ 下面是另一部分：
-
我在为分配从头创建的优先级队列类中有一个remove方法。我创建的优先级队列保存在一个数组中，索引从0开始。我跟踪等于数组长度的大小。remove方法使用名为的助手方法： 其中parent是数组中存储父元素的位置，我希望返回其最小的子元素。顺序就是每个非叶子节点的子节点数。我发现最小的代码: 它目前是我创建的PriorityQueue类的数组越界异常完整实现： Main包括我测试代码的3种不同方式
-
注意：我知道可以用比较器创建优先级队列，然后重复调用Add。