본문 바로가기

Programing

PriorityQueue는 어떻게 사용합니까?

PriorityQueue는 어떻게 사용합니까?


PriorityQueue정렬하려는 항목을 정렬하려면 어떻게해야 합니까?

또한 방법 offer차이점이 add있습니까?


Comparator<? super E> comparator정렬 순서에 적합한 방식으로 비교하는 비교자를 사용하여 생성자를 오버로드하십시오 . 정렬 방법에 대한 예제를 제공하는 경우 확실하지 않은 경우 비교기를 구현하는 샘플 코드를 제공 할 수 있습니다. (하지만 꽤 간단합니다.)

로 다른 곳 말했다되었습니다 : offeradd단지 다른 인터페이스 메소드 구현입니다. 내가 가진 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;
    }
}

출력은 다음과 같습니다.

짧은

매질

참으로 길다


자바 8 솔루션

Java 8에서 사용 lambda expression하거나 method reference도입 할 수 있습니다 . Priority Queue에 용량 값이 5 인 String 값이 저장되어있는 경우 인라인 비교기를 제공 할 수 있습니다 (String 길이 기준).

람다 식 사용

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 () vs add ()

당으로 문서

offer 메소드는 가능하면 요소를 삽입하고 그렇지 않으면 false를 리턴합니다. 이것은 점검되지 않은 예외를 던져야 만 요소를 추가 할 수없는 Collection.add 메소드와 다릅니다. 오퍼 방법은 고정 용량 (또는 "바운드 된") 큐에서와 같이 장애가 예외적으로 발생하는 것이 아니라 정상적인 경우에 사용하도록 설계되었습니다.

용량 제한 대기열을 사용하는 경우 일반적으로 offer ()가 add ()보다 선호되며, 예외를 throw해야만 요소를 삽입 할 수 없습니다. 그리고 PriorityQueue 인은 우선도 heap에 근거하는 무제한의 우선 순위 큐이다.


생성자 에게 적절하게 전달 Comparator하십시오 .

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

유일한 차이점 offeradd그들이 속한 인터페이스이다. offer인터페이스에 Queue<E>있지만 add원래는 Collection<E>인터페이스 있습니다. 그 외에도 두 방법 모두 정확히 동일한 작업을 수행합니다. 지정된 요소를 우선 순위 대기열에 삽입하십시오.


에서 큐 API :

offer 메소드는 가능하면 요소를 삽입하고 그렇지 않으면 false를 리턴합니다. 이것은 점검되지 않은 예외를 던져야 만 요소를 추가 할 수없는 Collection.add 메소드와 다릅니다. 오퍼 방법은 고정 용량 (또는 "바운드 된") 큐에서와 같이 장애가 예외적으로 발생하는 것이 아니라 정상적인 경우에 사용하도록 설계되었습니다.


javadoc에서 선언 한 것과 다르지 않습니다.

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

add()offer()질문 에 대답하기 만하면됩니다 (다른 질문은 완벽하게 답변을 받았으므로 그렇지 않을 수도 있음).

Queue 인터페이스의 JavaDoc에 따르면 , "제공 메소드는 가능한 경우 요소를 삽입하고 그렇지 않으면 false를 리턴합니다. 이는 Collection.add 메소드와 다르며, 점검되지 않은 예외를 던져서 만 요소를 추가 할 수 없습니다. offer 메소드는 다음을 위해 설계되었습니다. 예를 들어 고정 용량 (또는 "바운드 된") 큐에서 예외가 아닌 실패가 정상적인 경우에 사용합니다. "

즉, 요소를 추가 할 수 있으면 (PriorityQueue에서 항상 그러해야 함) 요소는 정확히 동일하게 작동합니다. 그러나 요소를 추가 할 수 없으면 offer()멋지고 예쁜 false반환을 제공하면서 add()코드에서 원하지 않는 불쾌한 예외를 throw합니다. 추가하지 못하면 코드가 의도 한대로 작동하거나 정상적으로 확인할 수있는 경우를 사용하십시오 offer(). 추가에 실패한 것이 문제가 있는 경우 Collection 인터페이스의 스펙add() 에 따라 발생하는 예외를 사용 하고 처리하십시오 .

이 방법 offer()false( 용량 제한 큐에서 선호되는 메소드) 를 리턴하여 실패 를 지정하는 큐 인터페이스 에서 계약을 완료하고 예외를 발생시켜 항상 실패지정add() 하는 콜렉션 인터페이스에서 계약을 유지 보수하는 방식으로 구현 됩니다 .

어쨌든, 그것은 적어도 질문의 그 부분을 분명히하기를 바랍니다.


여기에서 사용자 정의 비교기를 정의 할 수 있습니다 :

아래 코드 :

 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

오퍼와 추가 메소드의 차이점 : 링크


인쇄 주문도 궁금했습니다. 예를 들어이 경우를 고려하십시오.

우선 순위 대기열의 경우 :

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

이 코드는 :

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

다음과 다르게 인쇄 될 수 있습니다.

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

나는 토론에서 답을 발견 다른 포럼에서 사용자가 "라고 제안 () / 추가 ()는 큐에 요소를 삽입 방법. 당신이 예측 가능한 순서를 원하는 경우에 당신이 머리를 돌려 슬쩍 / 설문 조사를 사용해야합니다 "큐의."


를 사용하는 대신 구현Comparator 에서 사용중인 클래스를 가질 수도 있습니다 (따라서 메소드를 재정의하십시오 ).PriorityQueue ComparablecompareTo

예를 들어 개체를 연령별 로 정렬하는 유스 케이스가있는 경우 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

우선 순위 큐에는 각 요소에 우선 순위가 지정되어 있습니다. 우선 순위가 가장 높은 요소가 큐의 맨 위에 나타납니다. 이제 각 요소에 우선 순위를 지정하는 방법에 따라 다릅니다. 그렇지 않으면 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.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. 대신에 원하는 유형을 입력하십시오T

람다 사용 (자바 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를 바꾸십시오.

참고 URL : https://stackoverflow.com/questions/683041/how-do-i-use-a-priorityqueue