优先队列的另一种写法

Question

输入正文bobo老师，您在实现Dijkstra算法时，用pq存储了一个Node。我在做leetcode题目时发现，用如下更简洁的写法也ok

1	PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

相当于用pq存储了一个维度为2的数组，其中index为0表示的是顶点，1表示的距离。用lambda表达式确定pq的排序。不知道这种写法是不是不正式？在正式面试中可以接受吗？

第2个是我自己的一个观察。在做一般的BFS时，我们用queue实现，为了避免重复入队问题，所以visited和入队操作必须写在一起。也就是说，一个点入队后，马上要设置其visited为true，否则会重复入队，有时候数据量大会超时。而Dijkstra算法因为要不断update这个distance，所以重复入队反倒是必须的。

Answer 1

liuyubobobo 2022-06-16 01:52:55

1

可以的。面试也没问题。

不过这种写法是语言相关的。在 Java 中，可以把 int[] 视作一个对象。但是在一些语言中，比如 C++ 中，int[] 不是一个对象，所以类似 vector<int[]> 这样的写法是非法的。

另外，使用 Node 的另外一个优势是：可以存储多种不同的数据，包括将自定义的比较方式包含在内。是更加灵活且通用的。

但不管怎样，核心是：我们需要想办法把多个元素“集合”在一起，不管是使用 int[], Node，pair, tuple，ArrayList，LinkedList，甚至是 Map，等等等等各种方式，都可以让多个信息作为一个整体，扔进 pq 中。

2

首先，Dijkstra 不是一定要重复入队的。使用索引堆可以避免重复入队，进一步优化 Dijkstra 的复杂度。但是因为索引堆属于相对“高级”的数据结构，我在课程中也没有介绍。我在课程中介绍的 Dijkstra 算法已经足够应对所有的面试，甚至是所有的竞赛中的 Dijkstra 的问题了。（竞赛的难点不是这种“小的”优化，关键还是问题的建模。）

其次，非常重要的：在我介绍的这种 Dijkstra 算法中，虽然点会重复入队，但是这个重复和你说的 bfs 的重复不一样。

Dijkstra 的重复入队是有条件的：发现了一个到达当前点的更短的路径，也就是说当前的边可以松弛的时候，才可能重复入队。而由于最多每条边只可能松弛一次，所以入队的元素个数最多就是边数那么多。这就是 Dijkstra 算法中 logE 的来源。（P.S. 在我上面说的使用索引堆优化的 Dijkstra 算法中，这一项变为 logV，因为所有的点不会重复入队。）

但是对于 BFS，由于没有松弛的概念，所以重复入队意味着“遍历到”就入队，那就会出现无限的循环。a 和 b 相邻，从 a 走到 b，b 入队。从队里拿到 b，a 又和 b 相邻，a 又入队，这是一个无穷循环。

继续加油！：）

• 提问者 讲武德的年轻人 #1

  bobo老师，我想了一下，可能没有说清楚。我这里说的BFS和Dijkstra的区别，应该是设置visited为true的位置。在BFS中，我们在节点入队的时候就标记该节点为true。但是，如果把位置改为出队的时候标记为true，就会出现重复入队的问题。但是在Dijkstra中，因为不能保证每一个入队的节点都是最短距离，所以不能标记为true，必须在出队的时候标记。

• liuyubobobo 回复 提问者 讲武德的年轻人 #2

  明白了。关键还是你所说的 dijkstra 的重复入队，从边的角度看，不是重复，每一条边做松弛，就可能入队，一条边的松弛不可能入队两次，也就是 dijkstra 的点的重复入队，是有条件的，从边的角度看，是不重复的；但是 bfs 的重复，是真正的重复。（你说的标记位置解决了无限循环的问题，因为早晚会标记为 true，但是同一个点还是字不断地“无意义”地重复入队了。）