Java PriorityQueue与外部Map动态排序：理解其行为与高效实践

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class DijkstraExample {

    public static void main(String[] args) {
        int n = 5; // 假设有5个节点
        int s = 1; // 起始节点

        // 存储节点到起点的距离
        Map<Integer, Integer> distances = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            distances.put(i, Integer.MAX_VALUE); // 初始化为无穷大
        }
        distances.put(s, 0); // 起始节点距离为0

        // 创建PriorityQueue，根据distances中的值排序节点索引
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> distances.get(a) - distances.get(b));

        // 将所有节点加入队列
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }

        System.out.println("初始队列元素 (按优先级): " + queue); // 打印时顺序不一定正确，但poll()会取出最小的

        // 模拟Dijkstra算法中更新距离的场景
        // 假设找到了从s到节点3的更短路径，新距离为5
        int nodeToUpdate = 3;
        int newDistance = 5;

        // 问题：如果直接更新Map，PriorityQueue不会自动调整
        distances.put(nodeToUpdate, newDistance);
        System.out.println("更新Map后，队列元素 (poll()结果可能仍是旧优先级):");
        // 如果此时poll()，很可能取出的不是节点3，即使它现在距离最短
        // 除非它本来就是最短的，或者队列中没有其他元素比它更短

        // 为了验证，可以尝试poll()几个元素
        // System.out.println("Poll 1: " + queue.poll());
        // System.out.println("Poll 2: " + queue.poll());
    }
}

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class DijkstraCorrectExample {

    public static void main(String[] args) {
        int n = 5;
        int s = 1;

        Map<Integer, Integer> distances = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            distances.put(i, Integer.MAX_VALUE);
        }
        distances.put(s, 0);

        Queue<Integer> queue = new PriorityQueue<>((a, b) -> distances.get(a) - distances.get(b));

        // 初始将所有节点加入队列
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }

        System.out.println("初始队列元素 (poll()会取出最小的): " + queue.peek()); // 此时peek()应是1 (距离0)

        // 模拟Dijkstra算法中更新距离的场景
        // 假设找到了从s到节点3的更短路径，新距离为5
        int nodeToUpdate = 3;
        int newDistance = 5;

        System.out.println("\n--- 尝试更新节点 " + nodeToUpdate + " 的距离 ---");

        // 步骤1: 从队列中移除旧元素
        // 注意：remove(Object)操作的时间复杂度为O(N) + O(logN)
        boolean removed = queue.remove(nodeToUpdate);
        if (removed) {
            System.out.println("成功从队列中移除节点 " + nodeToUpdate);
        } else {
            System.out.println("节点 " + nodeToUpdate + 不在队列中，无需移除。");
        }

        // 步骤2: 更新外部Map中的优先级
        distances.put(nodeToUpdate, newDistance);
        System.out.println("Map中节点 " + nodeToUpdate + " 的新距离: " + distances.get(nodeToUpdate));

        // 步骤3: 将更新后的元素重新插入队列
        queue.offer(nodeToUpdate);
        System.out.println("重新将节点 " + nodeToUpdate + " 插入队列。");

        System.out.println("更新并重新插入后，队列中当前优先级最高的元素 (peek()): " + queue.peek());
        // 此时如果 nodeToUpdate (3, 距离5) 比其他还在队列中的元素距离更短，peek() 可能会是 3
        // 例如，如果其他所有节点距离都是 MAX_VALUE，那么3现在就是最短的
    }
}