java - 我如何在 Java 中实现使用不同类型的两个字段进行排序的元组优先级队列？

Question

我创建了一个名为 Thread 的类，它有两个字段:int index 和 long start_time，如下所示:

class Thread {
    public Thread(int index, long start_time) {
        this.index = index;
        this.start_time = start_time;
    }

    public int index;
    public long start_time;
}

之后，我创建了一个线程优先级队列，如下所示:

PriorityQueue<Thread> worker = new PriorityQueue<>();

所以，我要为这个队列提供 n 个线程，线程的编号从 0 到 n-1。它们都以 0 开头作为 start_time，如下所示:

for (int i = 0; i < numWorkers;i++){
            worker.add(new Threads(i , 0));
}  

稍后我会及时添加作业，假设作业是 {4 , 3}；如果 Pqueue 有 2 个元素 (0,0) 和 (1,0) 它将变成 (0,4) 和 (1,3) 因为 poll() 将选择 0 作为优先级(根据索引上升)但是下一次poll() 将首先弹出 (1,3)，因为 3 小于 4(因此它按 start_time 排序上升，但如果它们相等，则按索引排序上升)。

我只是在学习数据结构并使用 Comparable 和 Comparator，所以这是我第一次使用它，但大多数示例都没有提到元组，或者它们只是按一个字段排序。我的实现思路是这样的:

class threadComparator implements Comparator<Thread> {
    @Override
    public int compare(Thread a, Thread b) {
        if (a.start_time==b.start_time){
            return a.index - b.index;
        }
        return a.start_time - b.start_time;
    }
}

根据我的 IDE，我不能使用return a.start_time - b.start_time(需要不兼容的类型 int 找到 long)

我用了this page in CodeGeeks作为示例，但该示例不使用长类型。

最后，我应该如何将这个 threadComparator 包含在我的优先级队列中以应用此排序顺序？我假设是:

PriorityQueue<Thread> worker = new PriorityQueue<>(new threadComparator);

这样对吗？我应该在 threadComparator 类中还是在 Thread 类中实现 Comparator。请不要刻薄，我已经用谷歌搜索并在 SO 中进行了搜索，但我找不到类似的例子。希望我的解释足够清楚。

Answer 1

2个long值的减法是long类型的，这就是你不能返回的原因

a.start_time - b.start_time

另外请注意，如果允许负值，

a.index - b.index

和

a.start_time - b.start_time

可能溢出并返回无效结果。

最好像这样实现compare:

public int compare(Thread a, Thread b) {
    int c = Long.compare(a.start_time, b.start_time);
    return c == 0
                  ? Integer.compare(a.index, b.index) // compare index, if start_time is the same
                  : c; // if start_times are different, use the result of comparing the 2 fields
}

在 java 8 中，您还可以像这样构造一个比较器:

Comparator<Thread> comparator = Comparator.comparingLong(thread -> thread.start_time)
                                          .thenComparingInt(thread -> thread.index);