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

Question

我创建了一个名为 Thread 的 class，它有两个字段：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<>();

因此，我将向此队列提供编号从 0 到 n-1 的 n 个线程。它们都是以 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 作为例子，但那个例子没有使用 long 类型。

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

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

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

Answer 1

你几乎是在正确的道路上，但对于你的比较器，你必须 return int 值：

如果左侧较小则为负数
0 如果它们相等
如果右边较小则为正数

所以只需更换

return a.start_time - b.start_time;

来自

if (a.start_time < b.start_time)
   return -1;
if (a.start_time > b.start_time)
   return 1;
return 0;

Answer 2

2 long 值的减法是 long 类型，这就是为什么你不能 return

a.start_time - b.start_time

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

a.index - b.index

和

a.start_time - b.start_time

可能会溢出并 return 无效结果。

最好像这样实现 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);

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

How do I implement in Java a priority queue of a Tuple that sorts using both fields with different types?

java

priority-queue

comparator