使用优先队列（堆）实现Dijkstra算法的空间复杂度疑问

当用普通堆（比如二叉堆）实现Dijkstra算法，且不处理堆中的重复节点条目时，空间复杂度其实是O(E)，而非部分资料提到的O(V)。

具体原因如下：

• 普通堆的节点删除操作效率极低，所以实现时通常不会删除旧的无效条目，而是在发现更短路径时直接将新的（节点，当前最短距离）对加入堆中，后续遇到旧条目时直接跳过即可。
• 每条边最多会触发一次入堆操作：当边的起点被确定最短距离后，检查终点的距离，若能更新则将终点的新状态入堆。整个过程下来，堆内的条目数量最多等于图的边数E。
• 部分资料标注O(V)，要么是假设使用了支持高效删除的优先队列（比如斐波那契堆），要么只计算了存储节点距离、访问状态的数组这类O(V)的结构，完全忽略了堆本身的空间占用。但在普通堆的实际实现场景中，重复条目会让堆的空间复杂度达到O(E)级别。

内容的提问来源于stack exchange，提问作者JobHunter69