如何在java中使用优先级队列实现最大堆对

Question

我正在尝试用java实现具有键值对的Max堆。正如我们在C++中所知道的，我们可以用这种方式来做到这一点。。

priority_queue<pair<int, int> > pq;
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));

但我无法在java中做到这一点，请帮助我做到。

Answer 1

这里有一个示例讨论。

简单地说，您可以通过提供键值对并指定应该如何比较对来设置队列：

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

Answer 2

在Java中，您可以使用HashMap：

import javafx.util.Pair;
import java.util.PriorityQueue;
public class YourClass{
public static void main (String[] args){
int n = 3;
PriorityQueue<Pair<Integer,Integer> > pq = new PriorityQueue<Pair<Integer,Integer>>(n, Comparator.comparing(Pair::getKey));
/*Adding elements to HashMap*/
pq.add(new Pair <> (10, 200));
pq.add(new Pair <> (20, 100));
pq.add(new Pair <> (15, 400));
System.out.println(l.poll().getValue()); 
}
}

Answer 3

该对可用于来自javafx.util包的此用例。

如果我们需要根据值对其进行排序。

import javafx.util.Pair;
import java.util.*;
public class ExampleClass {
public static void main(String [] args) {
PriorityQueue<Pair<Integer, Integer>> maxHeap = new PriorityQueue<>((num1, num2) -> Integer.compare(num2.getValue(), num1.getValue()));
maxHeap.offer(new Pair<>(10, 200));
maxHeap.offer(new Pair<>(20, 100));
maxHeap.offer(new Pair<>(15, 400));
}
}

如果我们需要根据关键字对其进行排序。

import javafx.util.Pair;
import java.util.*;
public class ExampleClass {
public static void main(String [] args) {
PriorityQueue<Pair<Integer, Integer>> maxHeap = new PriorityQueue<>((num1, num2) -> Integer.compare(num2.getKey(), num1.getKey()));
maxHeap.offer(new Pair<>(10, 200));
maxHeap.offer(new Pair<>(20, 100));
maxHeap.offer(new Pair<>(15, 400));
}
}

在这里，我们通过传递一个简单的lambda表达式作为构造函数参数来创建优先级队列的实例。

我们可以使用while循环打印结果，以检查maxHeap是空的还是非空的。

while (!maxHeap.isEmpty()) {
Pair<Integer, Integer> topOfHeap = maxHeap.poll();
System.out.println(topOfHeap.getValue());
}