Java优先级队列

Question

如何使用java内置的优先级队列来读入和排序图的顶点，最终在每次迭代中删除最小边？

Answer 1

首先，创建为优先级队列比较：

class MinHeapComparator implements Comparator<Integer> { 
    @Override 
    public int compare(Integer one, Integer two) { 
    return mDistances[one] - mDistances[two];//... 
    } 
    } 

这是最短路径算法我写的。 mDistances是从源到顶点的距离。你可以修改比较器来比较你喜欢的方式。

从比较器的文档：“比较它的两个参数的顺序。返回一个负整数，零或一个正整数，因为第一个参数小于，等于或大于第二个参数。

完整的文档在这里：http://download.oracle.com/javase/1.5.0/docs/api/java/util/Comparator.html

二，项目添加到优先级队列。我通常使用包含顶点对象的数组构建一个图形，每个对象都包含其相邻顶点的列表。所以在我的情况下，我只是将索引添加到优先级队列来表示顶点。然后比较器可以包含逻辑来处理顶点。 PriorityQueue.add（）添加项目。

第三，实例化优先队列与比较：

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(numberItems, new MinHeapComparator()); 

第四，调用PriorityQueue.poll（）以提取关于堆顶部的项目。您的比较器用于确定堆顶部的项目。