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() 提取堆顶项目。您的比较器用于确定堆顶部的项目。