Java 如何使用 PriorityQueue？

Question

提问by Svish

How do I get a PriorityQueueto sort on what I want it to sort on?

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

Also, is there a difference between the offerand addmethods?

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

Answer 1

采纳答案by Jon Skeet

Use the constructor overload which takes a Comparator<? super E> comparatorand pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you're not sure. (It's pretty straightforward though.)

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

As has been said elsewhere: offerand addare just different interface method implementations. In the JDK source I've got, addcalls offer. Although addand offerhave potentiallydifferent behaviour in general due to the ability for offerto indicate that the value can't be added due to size limitations, this difference is irrelevant in PriorityQueuewhich is unbounded.

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

Here's an example of a priority queue sorting by string length:

以下是按字符串长度排序的优先级队列示例：

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

Here is the output:

这是输出：

short
medium
very long indeed

短的
中等的
确实很长

Answer 2

回答by dragonfly

Just pass appropriate Comparatorto the constructor:

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

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

The only difference between offerand addis the interface they belong to. offerbelongs to Queue<E>, whereas addis originally seen in Collection<E>interface. Apart from that both methods do exactly the same thing - insert the specified element into priority queue.

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

Answer 3

回答by d1ck50n

no different, as declare in javadoc:

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

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

Answer 4

回答by Peter

from Queue API:

来自队列 API：

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

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

Answer 5

回答by joserey

I was also wondering about print order. Consider this case, for example:

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

For a priority queue:

对于优先队列：

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

This code:

这段代码：

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

may print differently than:

打印方式可能不同于：

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

I found the answer from a discussion on another forum, where a user said, "the offer()/add() methods only insert the element into the queue. If you want a predictable order you should use peek/poll which return the head of the queue."

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

Answer 6

回答by Blueriver

Just to answer the add()vs offer()question (since the other one is perfectly answered imo, and this might not be):

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

According to JavaDoc on interface Queue, "The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues."

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

That means if you can add the element (which should always be the case in a PriorityQueue), they work exactly the same. But if you can't add the element, offer()will give you a nice and pretty falsereturn, while add()throws a nasty unchecked exception that you don't want in your code. If failure to add means code is working as intended and/or it is something you'll check normally, use offer(). If failure to add means something is broken, use add()and handle the resulting exception thrown according to the Collection interface's specifications.

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

They are both implemented this way to fullfill the contract on the Queue interface that specifies offer()fails by returning a false(method preferred in capacity-restricted queues) and also maintain the contract on the Collection interface that specifies add()always fails by throwing an exception.

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

Anyway, hope that clarifies at least that part of the question.

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

Answer 7

回答by akhil_mittal

Java 8 solution

Java 8 解决方案

We can use lambda expressionor method referenceintroduced in Java 8. In case we have some String values stored in the Priority Queue (having capacity 5) we can provide inline comparator (based on length of String) :

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

Using lambda expression

使用 lambda 表达式

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

Using Method reference

使用方法参考

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

Then we can use any of them as:

然后我们可以将它们中的任何一个用作：

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

This will print:

这将打印：

Apple
PineApple
Custard Apple

To reverse the order (to change it to max-priority queue) simply change the order in inline comparator or use reversedas:

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

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

We can also use Collections.reverseOrder:

我们还可以使用Collections.reverseOrder：

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

So we can see that Collections.reverseOrderis overloaded to take comparator which can be useful for custom objects. The reversedactually uses Collections.reverseOrder:

所以我们可以看到它Collections.reverseOrder被重载以获取对自定义对象有用的比较器。在reversed实际使用Collections.reverseOrder：

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

offer() vs add()

提供（）与添加（）

As per the doc

根据文档

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

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

When using a capacity-restricted queue, offer() is generally preferable to add(), which can fail to insert an element only by throwing an exception. And PriorityQueueis an unbounded priority queue based on a priority heap.

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

Answer 8

回答by devDeejay

Priority Queue has some priority assigned to each element, The element with Highest priority appears at the Top Of Queue. Now, It depends on you how you want priority assigned to each of the elements. If you don't, the Java will do it the default way. The element with the least value is assigned the highest priority and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily. You can also specify an ordering using Comparator in the constructorPriorityQueue(initialCapacity, comparator)

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

Example Code:

示例代码：

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

Output:

输出：

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

Else, You can also define Custom Comparator:

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

import java.util.Comparator;

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

Answer 9

回答by rashedcs

In here, We can define user defined comparator:

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

Below code :

下面的代码：

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

Output :

   india                                               
   pakistan                                         
   bangladesh

输出：

   india                                               
   pakistan                                         
   bangladesh

Difference between the offer and add methods : link

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

Answer 10

回答by KayV

Here is the simple example which you can use for initial learning:

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

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 如何使用 PriorityQueue？

提问by Svish

采纳答案by Jon Skeet

回答by dragonfly

回答by d1ck50n

回答by Peter

回答by joserey

回答by Blueriver

回答by akhil_mittal

Java 8 solution

Java 8 解决方案

offer() vs add()

提供（）与添加（）

回答by devDeejay

回答by rashedcs

回答by KayV

相关推荐

最近更新

标签

Java 如何使用 PriorityQueue？

提问by Svish

采纳答案by Jon Skeet

回答by dragonfly

回答by d1ck50n

回答by Peter

回答by joserey

回答by Blueriver

回答by akhil_mittal

Java 8 solution

Java 8 解决方案

offer() vs add()

提供（）与添加（）

回答by devDeejay

回答by rashedcs

回答by KayV

相关推荐

如何使用正则表达式来解析 Java 中的 HTML？

Java Spring Boot 访问静态资源缺少 scr/main/resources

是否有现有的库方法可以检查 Java 中的 String 是全部大写还是小写？

Java 预检响应中的 Access-Control-Allow-Methods 不允许总是得到 Method DELETE

相关推荐

最近更新

标签