Ubah priorityQueue menjadi max priorityqueue

Saya memiliki antrian prioritas di Java of Integers:

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

Ketika saya menelepon pq.poll()saya mendapatkan elemen minimum.

Pertanyaan: bagaimana cara mengubah kode untuk mendapatkan elemen maksimal?

Bagaimana kalau seperti ini:

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

The Collections.reverseOrder()menyediakan Comparatoryang akan mengurutkan unsur-unsur di PriorityQueuedalam urutan yang berlawanan untuk tatanan alam mereka dalam kasus ini.

Anda dapat menggunakan ekspresi lambda sejak Java 8.

Kode berikut akan mencetak 10, lebih besar.

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

Fungsi lambda akan mengambil dua bilangan bulat sebagai parameter masukan, menguranginya satu sama lain, dan mengembalikan hasil aritmatika. Fungsi lambda mengimplementasikan Antarmuka Fungsional Comparator<T>,. (Ini digunakan di tempat, sebagai lawan dari kelas anonim atau implementasi terpisah.)

Anda dapat memberikan Comparatorobjek khusus yang memberi peringkat elemen dalam urutan terbalik:

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

Sekarang, antrian prioritas akan membalikkan semua perbandingannya, jadi Anda akan mendapatkan elemen maksimum daripada elemen minimum.

Semoga ini membantu!

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

Di Java 8+ Anda dapat membuat antrian prioritas maksimal melalui salah satu metode berikut:

Metode 1:

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

Metode 2:

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

Metode 3:

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

Unsur-unsur antrian prioritas diurutkan menurut urutan aslinya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrian.

Pembanding harus mengganti metode perbandingan.

int compare(T o1, T o2)

Metode perbandingan default mengembalikan bilangan bulat negatif, nol, atau bilangan bulat positif karena argumen pertama kurang dari, sama dengan, atau lebih besar dari yang kedua.

Default PriorityQueue yang disediakan oleh Java adalah Min-Heap, Jika Anda ingin max heap berikut adalah kodenya

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

}

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

Berikut adalah contoh Max-Heap di Java:

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

Outputnya akan menjadi 10

Ini dapat dicapai dengan kode di bawah ini di Java 8 yang telah memperkenalkan konstruktor yang hanya membutuhkan pembanding.

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

Anda dapat menggunakan MinMaxPriorityQueue(ini adalah bagian dari pustaka Guava): berikut dokumentasinya . Sebagai gantinya poll(), Anda perlu memanggil pollLast()metode tersebut.

Ubah PriorityQueue menjadi MAX PriorityQueue Metode 1: Queue pq = new PriorityQueue <> (Collections.reverseOrder ()); Metode 2: Antrian pq1 = new PriorityQueue <> ((a, b) -> b - a); Mari kita lihat beberapa Contoh:

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

         */


    }
}

Mari kita ambil wawancara terkenal Masalah: Kth Largest Element in an Array menggunakan 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

 */
    }
}

Cara lain :

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

         */
    }
}

Seperti yang bisa kita lihat, keduanya memberikan hasil yang sama.

Ini dapat dicapai dengan menggunakan

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

Saya baru saja menjalankan simulasi Monte-Carlo pada kedua komparator pada tumpukan ganda jenis min max dan keduanya sampai pada hasil yang sama:

Ini adalah komparator maksimal yang telah saya gunakan:

(A) Koleksi pembanding bawaan

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

(B) Pembanding khusus

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

Anda dapat mencoba sesuatu seperti:

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

Yang berfungsi untuk fungsi perbandingan dasar lainnya yang mungkin Anda miliki.

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

Anda dapat mencoba mendorong elemen dengan tanda terbalik. Misalnya: Untuk menambahkan a = 2 & b = 5 dan kemudian polling b = 5.

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

Setelah Anda mengumpulkan kepala antrian, balikkan tanda untuk penggunaan Anda. Ini akan mencetak 5 (elemen yang lebih besar). Dapat digunakan dalam implementasi yang naif. Jelas bukan perbaikan yang andal. Saya tidak merekomendasikannya.

Kita bisa melakukan ini dengan membuat kelas CustomComparator kita yang mengimplementasikan antarmuka Comparator dan mengganti metode perbandingannya. Di bawah ini adalah kode yang sama:

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