java 排序优先队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13346551/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting PriorityQueue
提问by user1817988
I am having a problem with PriorityQueues, as I am lead to believe it orders on priority however I am not sure what the priority is (I mean what the value is and where it comes from). A priorityQueue can be made with a comparator in the constructor and I have tried this but it does not work.
我对 PriorityQueues 有问题，因为我相信它按优先级排序，但是我不确定优先级是什么（我的意思是值是什么以及它来自哪里）。可以在构造函数中使用比较器创建优先队列，我已经尝试过这个，但它不起作用。
Queue class:
队列类：
public JavaPriorityFlightQueue() {
super();
flights = new PriorityQueue(5, new SortQueueViaPriority());
}
Comparator:
比较器：
import java.util.Comparator;
public class SortQueueViaPriority implements Comparator {
public int compare(Object o1, Object o2){
Flight f1 = (Flight) o1;
Flight f2 = (Flight) o2;
if( f1 == null || f2 == null ){
if( f1 == f2 ) return 0;
else if( f2 == null) return +1;
else return -1;
}
Integer i1 = (Integer) f1.getPriority();
Integer i2 = (Integer) f2.getPriority();
return i2.compareTo(i1);
}
}
Priority is an int value which is part of the flight class. I test this.
Priority 是一个 int 值，它是航班类的一部分。我测试这个。
JavaPriorityFlightQueue flightQueue = new JavaPriorityFlightQueue();
Flight flight1 = new Flight("0001",9);
Flight flight2 = new Flight("0002",7);
Flight flight3 = new Flight("0003",1);
Flight flight4 = new Flight("0004",2);
Flight flight5 = new Flight("0005",1);
However the PriorityQueue is not sorted, and when I check it the value 9 is never compared to anything and the result is nothing is sorted. the compare class SortQueueViaPriority is copy and pasted from another class where the class sorts perfectly.
但是 PriorityQueue 没有排序，当我检查它时，值 9 永远不会与任何东西进行比较，结果是没有排序。比较类 SortQueueViaPriority 是从另一个类完美排序的类中复制和粘贴的。
回答by Peter Lawrey
I suggest you try the following example. If you use PriorityQueue as a queue, the entries are removed in order.
我建议你试试下面的例子。如果您使用 PriorityQueue 作为队列，则会按顺序删除条目。
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
public static void main(String... args) {
PriorityQueue<Flight> flights = new PriorityQueue<Flight>(5, new SortQueueViaPriority());
flights.add(new Flight("0001", 9));
flights.add(new Flight("0002", 7));
flights.add(new Flight("0003", 1));
flights.add(new Flight("0004", 2));
flights.add(new Flight("0005", 1));
while (!flights.isEmpty())
System.out.println(flights.remove());
}
}
class SortQueueViaPriority implements Comparator<Flight> {
@Override
public int compare(Flight f1, Flight f2) {
return Integer.compare(f2.getPriority(), f1.getPriority());
}
}
class Flight {
private final String name;
private final int priority;
Flight(String name, int priority) {
this.name = name;
this.priority = priority;
}
public int getPriority() {
return priority;
}
@Override
public String toString() {
return "Flight{" +
"name='" + name + '\'' +
", priority=" + priority +
'}';
}
}
prints
印刷
Flight{name='0001', priority=9}
Flight{name='0002', priority=7}
Flight{name='0004', priority=2}
Flight{name='0003', priority=1}
Flight{name='0005', priority=1}
Note: PriorityQueue sorts entries such that only the first element will be the smallest. If you iterate over the queue, you will see all the elements, but they may or may not be in order.
注意：PriorityQueue 对条目进行排序，以便只有第一个元素是最小的。如果您遍历队列，您将看到所有元素，但它们可能按顺序排列，也可能不按顺序排列。
回答by Amit Deshpande
Issue is Iterator.As Documented in Java doc of PriorityQueue#iterator
问题是Iterator.As 记录在Java doc of PriorityQueue#iterator
Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.
返回此队列中元素的迭代器。迭代器不会以任何特定顺序返回元素。
As toStringuses iterator it will not get printed in order. Or if you use loop based on iterator then also it will be in order.
由于toString使用迭代器，它不会按顺序打印。或者，如果您使用基于迭代器的循环，那么它也将是有序的。
And in the Java doc of PriorityQueue
The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
队列检索操作轮询、删除、查看和元素访问队列头部的元素。
To get results in order you will have to use one of these methods.
要按顺序获得结果，您必须使用其中一种方法。
回答by Chaitu
Instead of Comparatorjust use Comparableinterface.
而不是Comparator仅仅使用Comparable接口。
Your Flight class should implement Comparable interface. Then you need to override the compareTo()method. In that method you can add your own logic for sorting based on the property you need.
您的 Flight 类应该实现 Comparable 接口。然后您需要覆盖该compareTo()方法。在该方法中，您可以根据所需的属性添加自己的排序逻辑。
Just like this way:
就像这样：
@Override
public int compareTo(Object obj) {
// TODO Auto-generated method stub
Flight f = (Flight)obj;
if(this.a <f.a){
return 1;
}else{
return -1;
}
}
