爪哇。是否可以在优先级队列中使用一对，然后使用键作为优先级返回一个值

Question

所以我想使用最小的键作为优先级，然后返回对应键的值：

import javafx.util.Pair;
import java.util.PriorityQueue;

public class Test
{
    public static void main (String[] args)
    {
        int n = 5;

        PriorityQueue <Pair <Integer,Integer> > l = new PriorityQueue <Pair <Integer,Integer> > (n);

        l.add(new Pair <> (1, 90));
        l.add(new Pair <> (7, 54));
        l.add(new Pair <> (2, 99));
        l.add(new Pair <> (4, 88));
        l.add(new Pair <> (9, 89));

        System.out.println(l.poll().getValue()); 
    }
}

我寻找的输出是 90，因为 1 是最小的键。即使将该值用作优先级并返回键也很好，因为我可以在必要时交换数据。我想使用值/键作为优先级（在这种情况下是最小值）来显示键/值。我不知道在这种情况下如何做到这一点。这在 C++ 中工作正常。

Answer 1

您需要使用Comparatorwhich 将用于对此优先级队列进行排序。

创建时比较参数的使用Comparator.comparing()和传递Method referencePriorityQueue

PriorityQueue<Pair<Integer,Integer> > pq=
                new PriorityQueue<Pair<Integer,Integer>>(n, Comparator.comparing(Pair::getKey));

或者

您可以使用 lambda 表达式

PriorityQueue<Pair<Integer,Integer> > pq=
                    new PriorityQueue<Pair<Integer,Integer>>(n,(a,b) -> a.getKey() - b.getKey());

Answer 2

或者，使用Pair实现Comparable.

class Pair implements Comparable<Pair> {
    Integer value;
    Integer index;

    public Pair(Integer value, Integer index) {
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(Pair o) {
        return value - o.value;
    }
}

然后使用

// Add elements
queue.add(new Pair(valueKey, index));
// do it for all your elements

final Pair min = queue.poll();
Integer index = min.index;
Integer value = min.value;

// Do with them what you want.

我在 leetcode 挑战中使用了 PriorityQueue。 https://leetcode.com/problems/merge-k-sorted-lists/discuss/630580/Using-PriorityQueue-in-Java

这是完整的示例 https://github.com/yan-khonski-it/leetcode/blob/master/src/main/java/com/yk/training/leetcode/merge_sorted_lists/PriorityQueueSolution.java