排序优先队列

Question

我遇到了PriorityQueues的问题，据说它根据优先级排序，但是我不确定优先级是什么（我的意思是优先级的值和来源）。可以在构造函数中使用比较器创建PriorityQueue，我尝试过这样做，但是没有起作用。

队列类：

public JavaPriorityFlightQueue() {
    super();
    flights = new PriorityQueue(5, new SortQueueViaPriority());
}

比较器：

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);
    }
}

优先级是航班类的一部分，它是一个整数值。我正在测试这个。

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);

然而，PriorityQueue并没有排序。当我检查它时，值9从未与任何其他值进行比较，结果是什么都没有排序。比较类SortQueueViaPriority是从另一个类中复制粘贴过来的，在该类中，该类可以完美地进行排序。

- user1817988

---

请参考此答案：https://dev59.com/zXRB5IYBdhLWcg3wN1EQ - Miljen Mikic

Answer 1

我建议你尝试下面的示例。如果使用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 +
                '}';
    }
}

打印

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}

注意：PriorityQueue对条目进行排序，以使只有第一个元素是最小的。如果您遍历队列，则会看到所有元素，但它们可能或可能不按顺序排列。

- Peter Lawrey

---

@dacwe 正确，无论如何这就是OP实现的方式。 - Peter Lawrey

航班[flightID=0003，优先级=1] 航班[flightID=0005，优先级=1] 航班[flightID=0002，优先级=7] 航班[flightID=0001，优先级=9] 航班[flightID=0004，优先级=2] - user1817988

正如我在结尾处所指出的那样，这是可以预料的。 - Peter Lawrey

Answer 2

问题是Iterator。如PriorityQueue#iterator的Java文档中所述，返回此队列中元素的迭代器。该迭代器不以任何特定顺序返回元素。

由于toString使用迭代器，因此不会按顺序打印。或者，如果您基于迭代器使用循环，那么它也将按顺序。

在优先队列的Java文档中：

队列检索操作poll、remove、peek和element访问队列头部的元素。

要按顺序获取结果，您必须使用其中一种方法。

- Amit Deshpande

Answer 3

不要使用Comparator接口，而是使用Comparable接口。

你的Flight类应该实现Comparable接口。然后你需要覆盖compareTo()方法。在那个方法中，你可以根据你所需的属性添加自己的排序逻辑。

就像这样：

@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;
    }
}

- Chaitu