java - 如何使用优先队列？

Question

如何对PriorityQueue我想要排序的内容进行排序？

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

score 479 · Accepted Answer

使用构造函数重载，它接受 aComparator<? super E> comparator并传入一个比较器，该比较器以适合您的排序顺序的方式进行比较。如果你举一个你想如何排序的例子，如果你不确定，我们可以提供一些示例代码来实现比较器。（虽然这很简单。）

正如其他地方所说：offer并且add只是不同的接口方法实现。在我拥有的 JDK 源代码中，add调用offer. 尽管add和由于能够指示由于大小限制而无法添加值，因此通常offer具有潜在的不同行为，但这种差异与无界无关。offerPriorityQueue

这是一个按字符串长度排序的优先级队列示例：

// 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;
    }
}

这是输出：

短的

中等的

确实很长

score 90 · Accepted Answer

Java 8 解决方案

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

使用 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

要反转顺序（将其更改为最大优先级队列）只需更改内联比较器中的顺序或reversed用作：

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 方法插入一个元素，否则返回 false。这与 Collection.add 方法不同，后者只能通过抛出未经检查的异常才能添加元素。offer 方法设计用于当故障是正常而不是异常发生时使用，例如，在固定容量（或“有界”）队列中。

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

score 26 · Accepted Answer

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

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

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

score 19 · Accepted Answer

来自队列 API：

如果可能，offer 方法插入一个元素，否则返回 false。这与 Collection.add 方法不同，后者只能通过抛出未经检查的异常才能添加元素。offer 方法设计用于当故障是正常而不是异常发生时使用，例如，在固定容量（或“有界”）队列中。

score 15 · Accepted Answer

没有什么不同，正如在 javadoc 中声明的那样：

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

score 12 · Accepted Answer

传一个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。

score 6 · Accepted Answer

只是为了回答add()vsoffer()问题（因为另一个问题在 imo 中得到了完美的回答，而这可能不是）：

根据接口 Queue 上的 JavaDoc，“offer 方法在可能的情况下插入一个元素，否则返回 false。这与 Collection.add 方法不同，后者只能通过抛出未经检查的异常而无法添加元素。offer 方法设计用于当失败是正常而不是异常发生时使用，例如，在固定容量（或“有界”）队列中。”

这意味着如果您可以添加元素（在 PriorityQueue 中应该始终如此），它们的工作方式完全相同。但是如果你不能添加元素，offer()会给你一个不错的false回报，同时add()抛出一个你不希望在代码中出现的讨厌的未经检查的异常。如果未能添加意味着代码正在按预期工作和/或您将正常检查，请使用offer(). 如果添加失败意味着某些东西被破坏了，add()请根据Collection 接口的规范使用并处理引发的异常。

offer()它们都以这种方式实现，以通过返回一个false（容量受限队列中的首选方法）来完成指定失败的 Queue 接口上的合约，并维护 Collection 接口上的合约，该合约指定add()总是通过抛出异常而失败。

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

score 6 · Accepted Answer

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

下面的代码：

 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

报价和添加方法之间的区别：链接

score 4 · Accepted Answer

作为 using 的替代方法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

score 3 · Accepted Answer

我也想知道打印顺序。考虑这种情况，例如：

对于优先级队列：

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 返回头部队列中的。”

score 1 · Accepted Answer

优先级队列为每个元素分配了一些优先级，具有最高优先级的元素出现在队列顶部。现在，这取决于您希望如何为每个元素分配优先级。如果您不这样做，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

否则，您还可以定义自定义比较器：

import java.util.Comparator;

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

score 1 · Accepted Answer

这是您可以用于初始学习的简单示例：

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());
        }
    }

}

java - 如何使用优先队列？

12 回答 12

Java 8 解决方案

报价（）与添加（）

Related

Reference