如何使用priorityqueue?

xtfmy6hx  于 2021-07-04  发布在  Java
关注(0)|答案(12)|浏览(324)

我怎样才能得到一个 PriorityQueue 按我想要的排序?
另外,两者之间有区别吗 offer 以及 add 方法?

7ajki6be

7ajki6be1#

使用构造函数重载 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;
    }
}

以下是输出:
短的
中等的
很长时间了

hsgswve4

hsgswve42#

作为使用 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
3j86kqsm

3j86kqsm3#

没有什么不同,正如javadoc中声明的:

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

balp4ylt4#

只是为了回答问题 add()offer() 问题(因为另一个问题在国际海事组织得到了完美的回答,而这可能不是):
根据接口队列上的javadoc,“offer方法在可能的情况下插入一个元素,否则返回false。这与collection.add方法不同,collection.add方法只能通过引发未检查的异常来添加元素。offer方法设计用于故障是正常情况而不是异常情况时,例如在固定容量(或“有界”)队列中。”
这意味着如果您可以添加元素(在priorityqueue中应该总是这样),它们的工作原理完全相同。但如果你不能添加元素, offer() 会给你一个漂亮的 false 返回,而 add() 抛出代码中不希望出现的讨厌的未检查异常。如果添加失败意味着代码按预期工作和/或是您将正常检查的内容,请使用 offer() . 如果添加失败意味着有东西坏了,请使用 add() 并根据集合接口的规范处理引发的异常。
它们都以这种方式实现,以在指定 offer() 返回 false (容量受限队列中首选的方法)并在指定 add() 总是因为抛出异常而失败。
不管怎样,希望这至少能澄清问题的这一部分。

iswrvxsc

iswrvxsc5#

java 8解决方案

我们可以用 lambda expression 或者 method reference 在Java8中引入。如果我们在优先级队列中存储了一些字符串值(容量为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

要反转顺序(将其更改为最大优先级队列),只需在inline comparator或use中更改顺序 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()与add()

根据文件
offer方法在可能的情况下插入一个元素,否则返回false。这与collection.add方法不同,collection.add方法只能通过引发未检查的异常来添加元素。offer方法是为在故障是正常的而不是异常的情况下使用而设计的,例如在固定容量(或“有界”)队列中。
当使用容量受限的队列时,offer()通常比add()更可取,add()只能通过抛出异常来插入元素。priorityqueue是一个基于优先级堆的无限优先级队列。

8wigbo56

8wigbo566#

只要通过适当的 Comparator 致施工单位:

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

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

aemubtdh

aemubtdh7#

把它传给我 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。

kmbjn2e3

kmbjn2e38#

下面是一个简单的示例,您可以使用它进行初步学习:

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

}
uurity8g

uurity8g9#

我还想知道印刷顺序。例如,考虑以下情况:
对于优先级队列:

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

7rfyedvj

7rfyedvj10#

从队列api:
offer方法在可能的情况下插入一个元素,否则返回false。这与collection.add方法不同,collection.add方法只能通过引发未检查的异常来添加元素。offer方法是为在故障是正常的而不是异常的情况下使用而设计的,例如在固定容量(或“有界”)队列中。

gzszwxb4

gzszwxb411#

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

bwleehnv12#

在这里,我们可以定义用户定义的比较器:
以下代码:

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方法的区别:link

相关问题