在过去的一个星期里，我一直在研究dijkstra的算法，我在java中有正确的运行代码。它使用数组来计算标准findMin函数，它给你最小距离的顶点。显然它是O（n），现在我正在寻找使用优先级队列（最小堆）来实现它
我的思考过程是什么：
while (there are unseen Vertex)
{
vertex= get TheVertex WithSmallest Distance Yet;//(In can be done in O(log n) using heap)
for this vertex {
find all of the adjacent edges and traverse them.
for a particular vertex which is not there in heap yet{
Simply add it in the queue;
}
}
}
但是如果堆中存在特定的顶点，那么它的距离可能会根据找到的Min节点的距离进行更新。
现在我的问题是如何在O（log n）时间内更新堆中的特定元素。
我们不能在O（1）时间内找到那个元素，对吗？
在我像我这样天真的实现中，它将是O（n），
那么，有人能建议如何处理这个瓶颈吗？我们如何在O（log n）时间内更新Heap中的特定顶点？（类似地，我们如何在O（1）时间内找到特定元素）
我知道解决这种情况的两种基本方法：
>
无论何时访问顶点的邻居，都要将它们插入堆中，无论它们是否在堆中。然后，当您获得离堆距离最小的顶点时，检查它是否已经从堆中删除。如果有，则将其也删除并继续。否则，将其标记为已删除并访问所有邻居。
保留一个显式指针，指向每个元素在堆中的位置。然后您可以对已经定位的元素执行称为“减少键”的操作。
