priorityQueue를 최대 priorityqueue로 변경

priorityQueue를 최대 priorityqueue로 변경

---

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()제공 Comparator의 요소 정렬 할 것이라고 PriorityQueue이 경우 자연 순서 a를 oposite 순서를.

---

Java 8부터 람다 식을 사용할 수 있습니다.

다음 코드는 더 큰 10을 인쇄합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
pq.add(10);
pq.add(5);
System.out.println(pq.peek());

람다 함수는 두 개의 정수를 입력 매개 변수로 취하고 서로 빼고 산술 결과를 반환합니다. 람다 함수는 기능 인터페이스 인 Comparator<T>. (이는 익명 클래스 또는 개별 구현과 달리 제자리에서 사용됩니다.)

---

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에서 제공하는 기본 PriorityQueue는 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 ()

---

다음은 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입니다.

---

You can use MinMaxPriorityQueue (it's a part of the Guava library): here's the documentation. Instead of poll(), you need to call the pollLast() method.

---

Change PriorityQueue to MAX PriorityQueue Method 1 : Queue pq = new PriorityQueue<>(Collections.reverseOrder()); Method 2 : Queue pq1 = new PriorityQueue<>((a, b) -> b - a); Let's look at few Examples:

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

         */


    }
}

Let's take a famous interview Problem : Kth Largest Element in an Array using PriorityQueue

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

 */
    }
}

Another way :

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

         */
    }
}

As we can see, both are giving the same result.

---

I just ran a Monte-Carlo simulation on both comparators on double heap sort min max and they both came to the same result:

These are the max comparators I have used:

(A) Collections built-in comparator

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

(B) Custom comparator

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

---

You can try something like:

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

Which works for any other base comparison function you might have.

---

This can be achieved by the below code in Java 8 which has introduced a constructor which only takes a comparator.

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

---

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

---

This can be achieved by using

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

---

You can try pushing elements with reverse sign. Eg: To add a=2 & b=5 and then poll b=5.

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

Once you poll the head of the queue, reverse the sign for your usage. This will print 5 (larger element). Can be used in naive implementations. Definitely not a reliable fix. I don't recommend it.

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