우선순위 변경최대 우선 순위 큐로 대기열 지정

우선순위 변경최대 우선 순위 큐로 대기열 지정

Java of Integers에 우선 순위 대기열이 있음:

 PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

내가 전화할 때pq.poll()나는 최소한의 요소를 얻는다.

질문: 최대 요소를 얻기 위해 코드를 변경하는 방법?

이렇게 하는 게 어때?

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

그Collections.reverseOrder()a를 제공하다.Comparator그 원소들을 분류할 수 있는PriorityQueue이 경우 자연적 순서에 따라 오포사이트 순서로

자바 8부터 람다 식을 사용할 수 있다.

다음 코드는 10을 더 크게 인쇄할 것이다.

// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

PriorityQueue<Integer> pq =new PriorityQueue<>((x, y) -> Integer.compare(y, x));

pq.add(10);
pq.add(5);
System.out.println(pq.peek());

람다 함수는 입력 파라미터로 두 개의 Integers를 취하여 서로 빼서 산술 결과를 반환한다.람다 함수는 기능 인터페이스를 구현하며,Comparator<T> (에 사용된다 (이것은 익명의 수업이나 별개의 실행과는 반대로 제자리에 사용된다.)

Java 8+에서는 다음 방법 중 하나를 사용하여 최대 우선 순위 대기열을 만들 수 있다.

방법 1:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder()); 

방법 2:.

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a); 

방법 3:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a)); 

사용자 정의 제공 가능Comparator요소를 역순으로 정렬하는 객체:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs < rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});

우선 순위 대기열은 모든 비교를 반대로 하므로 최소 요소보다는 최대 요소를 얻게 된다.

이것이 도움이 되기를!

PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);

우선 순위 대기열의 요소는 자연 순서 또는 대기열 구성 시간에 제공된 비교기에 따라 정렬된다.

비교기는 비교 방법을 재정의해야 한다.

int compare(T o1, T o2)

기본 비교 방법은 첫 번째 변수가 두 번째 변수보다 작거나 같거나 크면 음의 정수, 0 또는 양의 정수를 반환한다.

기본 우선 순위Java에서 제공하는 대기열은 Min-Heap이며, 다음 최대 힙을 원하는 경우 코드

public class Sample {
    public static void main(String[] args) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            public int compare(Integer lhs, Integer rhs) {
                if(lhs<rhs) return +1;
                if(lhs>rhs) return -1;
                return 0;
            }
        });
        q.add(13);
        q.add(4);q.add(14);q.add(-4);q.add(1);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

참조: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

비교기 인터페이스를 구현하는 CustomComparator 클래스를 생성하고 비교 방법을 재정의함으로써 이 작업을 수행할 수 있다.아래는 동일한 코드에 대한 것이다.

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}

이는 다음을 사용하여 달성할 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

다음은 Java의 Max-Heap 샘플이다.

PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
if (x < y) return 1;
if (x > y) return -1;
return 0;
}
});
pq1.add(5);
pq1.add(10);
pq1.add(-1);
System.out.println("Peek: "+pq1.peek());

생산량은 10이 될 것이다.

이는 대조약만 사용하는 생성자를 도입한 자바 8의 아래 코드로 달성할 수 있다.

PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());

사용할 수 있다MinMaxPriorityQueue(Guava 라이브러리의 일부임):여기 서류야대신에poll(), 당신은 전화할 필요가 있다.pollLast()방법의

우선 순위 변경최대 우선 순위로 대기열 지정대기열 방법 1 : 대기열 pq = 새 우선순위대기열<>(Collections.reverseOrder(); 방법 2 : 대기열 pq1 = 새 우선순위대기열(a, b) - b - a); 몇 가지 예를 보자.

public class Example1 {
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        System.out.println("......................");
        // another way
        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        /* OUTPUT
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
          Max element in the list => 888
          ......................
           Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
           Max element in the list => 888

         */


    }
}

유명한 인터뷰 문제: 우선순위를 사용하는 배열에서 K번째 가장 큰 요소큐

public class KthLargestElement_1{
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        while (--k > 0) {
            pq.poll();
        } // while
        System.out.println("Third largest => " + pq.peek());
/*
 Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666

 */
    }
}

다른 방법:

public class KthLargestElement_2 {
    public static void main(String[] args) {
        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;

        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        while (--k > 0) {
            pq1.poll();
        } // while
        System.out.println("Third largest => " + pq1.peek());
        /*
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222] 
          Max element in the list => 888 
          Third largest => 666

         */
    }
}

우리가 알 수 있듯이, 둘 다 같은 결과를 주고 있다.

방금 두 대조군에 대한 Monte-Carlo 시뮬레이션을 이중 힙 정렬 최소값으로 실행했는데 둘 다 동일한 결과를 얻었다.

다음은 내가 사용한 최대 대조약이다.

(가) 내장 대조군 수집

 PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());

(나) 사용자 정의 비교기

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
    int compare(Integer lhs, Integer rhs) {
        if (rhs > lhs) return +1;
        if (rhs < lhs) return -1;
        return 0;
    }
});

다음과 같은 방법을 시도해 보십시오.

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));

다른 기본 비교 기능에 사용할 수 있는 기능.

PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));

람다를 사용하여 -1로 결과를 곱하면 최대 우선 순위 대기열을 얻을 수 있다.

PriorityQueue<> q = new PriorityQueue<Integer>(
                       (a,b) ->  -1 * Integer.compare(a, b)
                    );

역기호로 요소들을 밀어볼 수 있다.예: a=2&b=5를 추가한 다음 b=5를 폴링한다.

PriorityQueue<Integer>  pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());

일단 당신이 큐의 머리를 폴링하고 나면, 당신의 사용을 위해 그 기호를 뒤집어라.이렇게 하면 5(더 큰 요소)가 인쇄된다.순진한 구현에 사용할 수 있다.확실히 믿을만한 해결책은 아니다.나는 그것을 추천하지 않는다.

• 우선 순위를 되돌리는 간단한 방법Java의 Collections.reverseOrder()를 사용하여 대기열에 넣으십시오.

-> 내게 우선권이 있다.대기열:(예:)

    PriorityQueue<String> pQueue = new PriorityQueue<>();
    
    pQueue.add("Honda");
    pQueue.add("Passion");
    pQueue.add("Heroni");
    pQueue.add("Ola");

-> 새 우선순위 작성역방향 어레이 저장소를 위한 대기열.

  PriorityQueue<String> pRqueue = new 
              PriorityQueue<String>(pQueue.size(), Collections.reverseOrder());

-> Syntex pQueue.size()는 이미 선언된 배열이므로 여기에 크기만 주어라.

-> 이전 대기열의 요소를 새 대기열에 추가:

  pRqueue.addAll(pQueue);

-> 이제 큐를 인쇄한다.및 출력은 아래와 같다.

    Queue Element:[ Heroni, Ola, Honda, Passion ]
    Reverese PriorityQueue Element:[ Passion, Ola, Honda, Heroni ]

☻ 완료.코드를 유지하십시오.

참조URL: https://stackoverflow.com/questions/11003155/change-priorityqueue-to-max-priorityqueue