java Java中对象的优先级队列

Priority queues of objects in Java

提问by MNM

Hello Im a bit lost n the priority queues and comparator. I dont really see how to make a comparator in java So what I have is giving me a error and what I have read is no help to me http://www.tutorialspoint.com/java/java_using_comparator.htmThis post game me some ideas but Im still stuck on how to do it How do I use a PriorityQueue?

你好，我在优先队列和比较器中有点迷失了。我真的不知道如何在 Java 中制作比较器 所以我给了我一个错误，我读到的内容对我没有帮助 http://www.tutorialspoint.com/java/java_using_comparator.htm这篇文章给我一些想法，但我仍然坚持 如何去做我如何使用 PriorityQueue？

What i have is a class that creates an object with a priority, arrival time, and finish time. I also have a number of priority queues to place them into. When i start I place them into the arrival queue to sort them and then see which one came in first and place that into the queue one. But when I try to add a second one to the arrival queue it fails and throws an exception. What I want to do first is to add all the processes to the arrival queue and then sort them so the one with the smallest arrival time will be the first one out of the arrival queue and into the queue one. Thanks for any help with this

我所拥有的是一个创建具有优先级、到达时间和完成时间的对象的类。我还有一些优先级队列可以放置它们。当我开始时，我将它们放入到达队列以对它们进行排序，然后查看哪个先进入并将其放入队列中。但是当我尝试将第二个添加到到达队列时，它会失败并引发异常。我首先要做的是将所有进程添加到到达队列中，然后对它们进行排序，以便到达时间最短的进程将是到达队列中的第一个进入队列的第一个。感谢您对此的任何帮助

    //the comparator
    Comparator<Integer> comparator = new Comparator();
    //priority queues
    //only needs 10 elements to  hold
    PriorityQueue one = new PriorityQueue(10, comparator);
    PriorityQueue two = new PriorityQueue(10, comparator);
    PriorityQueue three = new PriorityQueue(10, comparator);
    PriorityQueue four = new PriorityQueue(10, comparator);
    PriorityQueue arrival = new PriorityQueue(10, comparator);

    //put all processes in arrival queue
    arrival.add(p1);
    arrival.add(p2);
    arrival.add(p3);
    arrival.add(p4);
    arrival.add(p5);
    arrival.add(p6);
    arrival.add(p7);
    arrival.add(p8);
    arrival.add(p9);
    arrival.add(p10);

回答by Andrzej Doyle

Let's look at how you're defining Comparator, because at the moment I don't think what you've written would even compile.

让我们看看您如何定义Comparator，因为目前我认为您编写的内容甚至无法编译。

Comparatoris an interface, meaning that you need to define a classthat implements it. That is, you need to define a class that has concrete implementations of the methods described by the interface. Here, there's only one method you need to worry about - compare. (The interface also defines equals, but that's an odd choice since it's equal to the one on Objectand so every class will implement this by default...)

Comparator是一个接口，这意味着您需要定义一个实现它的类。也就是说，您需要定义一个类，该类具有接口描述的方法的具体实现。在这里，您只需要担心一种方法 - compare。（接口也定义了equals，但这是一个奇怪的选择，因为它等于 on Object，所以每个类都会默认实现这个......）

The comparemethod takes two objects of the target type, and decides which one of them comes "before" the other. It returns:

该compare方法采用目标类型的两个对象，并决定其中一个“先于”另一个。它返回：

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

负整数、零或正整数作为第一个参数小于、等于或大于第二个参数。

So - you want to compare objects of whatever the class of your p1, p2instances are (I'll call it MyClass). That means that you have to define a class:

所以 - 你想比较你的p1,p2实例是什么类的对象（我称之为MyClass）。这意味着您必须定义一个类：

class MyComparator implements Comparator<MyClass> {

    public int compare(MyClass a, MyClass b) {
        // TODO
    }
}

We know that the compare method should return a value depending on which of the MyClassarguments comes before the other one. You've said in your question that the one that comes first, is the one that has the smallest (i.e. earliest?) arrival time.

我们知道 compare 方法应该根据哪个MyClass参数在另一个参数之前返回一个值。你在你的问题中说过，最先出现的是到达时间最短（即最早？）的那个。

This is actually very easy, because that's the so-called natural orderingon java.util.Dateobjects - so you can just compare their arrival times against each other directly, as the result of thatcomparison is the same as the overall comparison.

这其实是很容易的，因为这就是所谓的自然顺序上java.util.Date的对象-所以你可以直接比较它们的到达时间对对方，结果是比较相同的整体比较。

Therefore the implementation of comparecan simply be (assuming a sensibly-named accessor method):

因此， 的实现compare可以简单地是（假设一个合理命名的访问器方法）：

public int compare(MyClass a, MyClass b) {
    return a.getStartTime().compareTo(b.getStartTime());
}

And there you go! You've just defined your own comparator, that will sort MyClassobjects by start time ascending. You can use it in the priority queues similarly to what you have already:

你去吧！您刚刚定义了自己的比较器，它将MyClass按开始时间升序对对象进行排序。您可以在优先级队列中使用它，类似于您已经拥有的：

Comparator<MyClass> comparator = new MyComparator();
PriorityQueue<MyClass> arrival = new PriorityQueue<MyClass>(10, comparator);