Java中对象的优先级队列

Question

你好我有点失去了优先级队列和比较器.我真的没有看到如何在java中制作比较器所以我所拥有的是给我一个错误,而我所读到的内容对我没有帮助 http://www.tutorialspoint.com/java/java_using_comparator.htm 这个帖子游戏我一些想法,但我仍然坚持如何做它 如何使用PriorityQueue？

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

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

Answer 1

让我们来看看你是如何定义的Comparator,因为目前我不认为你写的内容甚至会编译.

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

该compare方法采用目标类型的两个对象,并确定它们中的哪一个"先于"另一个.它返回:

第一个参数的负整数,零或正整数小于,等于或大于第二个参数.

所以-你要比较的类你的任何对象p1,p2实例是(我称之为MyClass).这意味着你必须定义一个类:

class MyComparator implements Comparator<MyClass> {

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

我们知道compare方法应该返回一个值,这取决于哪个MyClass参数在另一个之前.你在问题中已经说过,首先出现的是那个具有最小(即最早？)到达时间的那个.

这实际上非常简单,因为这就是对象上所谓的自然排序java.util.Date - 所以你可以直接比较它们的到达时间,因为这种比较的结果与整体比较相同.

因此,实现compare可以简单地(假设一个明智的命名访问器方法):

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

你去吧!您刚刚定义了自己的比较器,它将MyClass按开始时间升序对对象进行排序.您可以在优先级队列中使用它,与您已经使用的类似:

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