我如何使用优先队列?

如何让PriorityQueue对我想要它排序的东西进行排序?

另外，offer和add方法之间有区别吗?

652319 次浏览
小开
最佳答案

使用构造函数重载，它接受Comparator<? super E> comparator并传入一个比较器，该比较器以适当的方式对排序顺序进行比较。如果你给出一个你想要如何排序的例子，如果你不确定的话，我们可以提供一些示例代码来实现比较器。(其实很简单。)

正如在其他地方所说:offer和add只是不同的接口方法实现。在JDK源代码中，add调用offer。虽然add和offer通常具有潜在的不同的行为，因为offer能够指示由于大小限制而不能添加值，但这种差异在PriorityQueue中是无关的，因为它是无界的。

下面是一个优先级队列按字符串长度排序的例子:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;


public class Test {
public static void main(String[] args) {
Comparator<String> comparator = new StringLengthComparator();
PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
queue.add("short");
queue.add("very long indeed");
queue.add("medium");
while (queue.size() != 0) {
System.out.println(queue.remove());
}
}
}


// StringLengthComparator.java
import java.util.Comparator;


public class StringLengthComparator implements Comparator<String> {
@Override
public int compare(String x, String y) {
// Assume neither string is null. Real code should
// probably be more robust
// You could also just return x.length() - y.length(),
// which would be more efficient.
if (x.length() < y.length()) {
return -1;
}
if (x.length() > y.length()) {
return 1;
}
return 0;
}
}

输出如下:

短

媒介

确实很长

小开

只需将适当的Comparator传递给构造函数:

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

offer和add之间的唯一区别是它们所属的接口。offer属于Queue<E>，而add最初出现在Collection<E>接口中。除此之外，这两种方法做的事情完全相同——将指定的元素插入优先级队列。

小开

没有区别，正如在javadoc中声明的那样:

public boolean add(E e) {
return offer(e);
}
小开

从队列API:

offer方法尽可能插入一个元素，否则返回false。这与合集不同。方法，该方法只能通过抛出未经检查的异常来添加元素。offer方法设计用于故障是正常情况，而不是异常情况，例如在固定容量(或“有界”)队列中。

小开

我还想知道打印订单的问题。举个例子:

对于优先级队列:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

这段代码:

pq3.offer("a");
pq3.offer("A");

可能打印不同于:

String[] sa = {"a", "A"};
for(String s : sa)
pq3.offer(s);

我从一个讨论在另一个论坛中找到了答案，其中一个用户说，“offer()/add()方法只将元素插入队列。如果你想要一个可预测的顺序，你应该使用peek/poll来返回队列的头。”

小开

只是为了回答add() vs offer()的问题(因为在我看来，另一个问题已经完美地回答了，而这个可能不是):

根据接口Queue上的JavaDoc，“offer方法在可能的情况下插入一个元素，否则返回false。这与合集不同。方法，该方法只能通过抛出未经检查的异常来添加元素。offer方法设计用于故障是正常情况，而不是异常情况，例如在固定容量(或“有界”)队列中。”

这意味着如果您可以添加元素(在PriorityQueue中应该总是这样)，它们的工作方式完全相同。但是如果你不能添加元素，offer()将给你一个漂亮的false返回，而add()抛出一个讨厌的未检查异常，你不希望在你的代码中。如果添加失败意味着代码按预期工作和/或它是你正常检查的东西，使用offer()。如果添加失败意味着出错，则使用add()并根据Collection接口的规范处理引发的结果异常。

它们都是这样实现的，在Queue接口上通过返回false (在有容量限制的队列中首选的方法)来实现指定offer()失败的契约，并在Collection接口上维护指定add()总是抛出异常而失败的契约。

无论如何，希望这至少澄清了问题的那一部分。

小开

Java 8解决方案

我们可以使用Java 8中引入的lambda expression或method reference。如果我们有一些String值存储在优先队列中(容量为5)，我们可以提供内联比较器(基于String的长度):

使用lambda表达式

PriorityQueue<String> pq=
new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

使用方法参考

PriorityQueue<String> pq=
new PriorityQueue<String>(5, Comparator.comparing(String::length));

然后我们可以使用它们中的任何一个:

public static void main(String[] args) {
PriorityQueue<String> pq=
new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
// or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
pq.add("Apple");
pq.add("PineApple");
pq.add("Custard Apple");
while (pq.size() != 0)
{
System.out.println(pq.remove());
}
}

这将打印:

Apple
PineApple
Custard Apple

要反转顺序(将其更改为max-priority queue)，只需在内联比较器中更改顺序或使用reversed as:

PriorityQueue<String> pq = new PriorityQueue<String>(5,
Comparator.comparing(String::length).reversed());

我们也可以使用Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5,
Collections.reverseOrder(Comparator.comparing(String::length))

因此，我们可以看到Collections.reverseOrder被重载以接受比较器，这对自定义对象很有用。reversed实际上使用了Collections.reverseOrder:

default Comparator<T> reversed() {
return Collections.reverseOrder(this);
}

Offer () vs add()

根据医生

offer方法在可能的情况下插入一个元素，否则返回 假的。这与合集不同。方法，该方法可能失败 仅通过抛出未经检查的异常来添加元素。报价 方法是为失败是正常使用而设计的，而不是 异常发生，例如在固定容量(或“有界”)中 队列。< / p >

在使用有容量限制的队列时，offer()通常比add()更可取，后者只能通过抛出异常而无法插入元素。PriorityQueue是一个基于优先级堆的无界优先级队列。

小开

优先级队列为每个元素分配了一些优先级，具有最高优先级的元素出现在队列的顶部。这取决于你想如何给每个元素分配优先级。如果不这样做，Java将以默认方式执行。具有最小值的元素被赋予最高优先级，因此首先从队列中删除。如果有几个具有相同最高优先级的元素，则可以任意地打破连接。还可以在构造函数中使用Comparator指定排序 PriorityQueue(initialCapacity, comparator)

示例代码:

PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
System.out.print(queue2.remove() + " ");
}

输出:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia

除此之外，你还可以定义Custom Comparator:

import java.util.Comparator;


public class StringLengthComparator implements Comparator<String>
{
@Override
public int compare(String x, String y)
{
//Your Own Logic
}
}
小开

在这里，我们可以定义用户定义的比较器:

以下代码:

 import java.util.*;
import java.util.Collections;
import java.util.Comparator;




class Checker implements Comparator<String>
{
public int compare(String str1, String str2)
{
if (str1.length() < str2.length()) return -1;
else                               return 1;
}
}




class Main
{
public static void main(String args[])
{
PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());
queue.add("india");
queue.add("bangladesh");
queue.add("pakistan");
 

while (queue.size() != 0)
{
System.out.printf("%s\n",queue.remove());
}
}
}

输出:

   india
pakistan
bangladesh

offer和add方法的区别:链接

小开

下面是一个简单的例子，你可以用它来进行初步学习:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;


public class PQExample {


public static void main(String[] args) {
//PriorityQueue with Comparator
Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
addToQueue(cpq);
pollFromQueue(cpq);
}


public static Comparator<Customer> idComp = new Comparator<Customer>(){


@Override
public int compare(Customer o1, Customer o2) {
return (int) (o1.getId() - o2.getId());
}


};


//utility method to add random data to Queue
private static void addToQueue(Queue<Customer> cq){
Random rand = new Random();
for(int i=0;i<7;i++){
int id = rand.nextInt(100);
cq.add(new Customer(id, "KV"+id));
}
}




private static void pollFromQueue(Queue<Customer> cq){
while(true){
Customer c = cq.poll();
if(c == null) break;
System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
}
}


}
小开

作为使用Comparator的替代方法，你也可以让你在PriorityQueue中使用的类实现Comparable(并相应地重写compareTo方法)。

注意，如果顺序是对象的直观顺序，通常最好只使用Comparable而不是Comparator——例如，如果你有一个用例要按年龄对Person对象排序，那么最好只使用Comparator。

import java.lang.Comparable;
import java.util.PriorityQueue;


class Test
{
public static void main(String[] args)
{
PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
queue.add(new MyClass(2, "short"));
queue.add(new MyClass(2, "very long indeed"));
queue.add(new MyClass(1, "medium"));
queue.add(new MyClass(1, "very long indeed"));
queue.add(new MyClass(2, "medium"));
queue.add(new MyClass(1, "short"));
while (queue.size() != 0)
System.out.println(queue.remove());
}
}

class MyClass implements Comparable<MyClass>
{
int sortFirst;
String sortByLength;


public MyClass(int sortFirst, String sortByLength)
{
this.sortFirst = sortFirst;
this.sortByLength = sortByLength;
}


@Override
public int compareTo(MyClass other)
{
if (sortFirst != other.sortFirst)
return Integer.compare(sortFirst, other.sortFirst);
else
return Integer.compare(sortByLength.length(), other.sortByLength.length());
}


public String toString()
{
return sortFirst + ", " + sortByLength;
}
}

输出:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed
小开

给它传递一个Comparator。填入你想要的类型来代替T

使用lambdas (Java 8+):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

经典的方法，使用匿名类:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {


@Override
public int compare(T e1, T e2) {
return e1.compareTo(e2);
}


});

要按相反的顺序排序，只需交换e1和e2。


提交答案