Bagaimana untuk menggunakan timbunan untuk menyelesaikan masalah Top-k di Jawa?

1. Apakah timbunan?

Struktur timbunan

Timbunan sebenarnya adalah pokok binari, tetapi pokok binari biasa menyimpan data dalam struktur rantai, manakala timbunan menyimpan data secara berurutan dalam tatasusunan. Jadi apakah jenis pokok binari yang sesuai untuk penyimpanan berjujukan?

Kami mengandaikan bahawa pokok binari biasa boleh disimpan dalam tatasusunan, maka kami boleh mendapatkan struktur berikut:

Kita dapat melihatnya apabila terdapat ruang di tengah-tengah nilai pokok binari, ruang penyimpanan tatasusunan akan terbuang, jadi dalam keadaan apakah ruang itu tidak akan dibazirkan? Itu adalah pokok binari yang lengkap.

Daripada struktur di atas, kami tidak boleh menggunakan penunjuk struktur rantai untuk mengakses nod anak atau nod induk Kami hanya boleh mengaksesnya melalui subskrip yang sepadan, iaitu sebenarnya agak mudah.

Contohnya, dalam gambar di bawah:

Diketahui bahawa subskrip nod 2 ialah 1, kemudian

Subskrip anak kirinya ialah: 2 * 2 + 1 = 3

Subskrip anak kanannya ialah: 2 * 2 + 2 = 4

Sebaliknya, diketahui subskrip nod 1 ialah 3 dan subskrip bagi nod 3 ialah 4, kemudian

1 nod ialah: (3 - 1) / 2 = 1

Subskrip nod induk bagi 3 nod ialah: (4 - 1) / 2 = 1

Timbunan akar besar VS timbunan akar kecil

Timbunan akar besar (timbunan maksimum)

Akar besar heap menjamin bahawa nod akar setiap pokok binari adalah lebih besar daripada nod anak kiri dan kanan

Mula melaraskan dari nod akar subpokok terakhir, ke nod akar setiap subpokok, supaya setiap subpokok dilaraskan ke bawah ke dalam timbunan akar yang besar, dan akhirnya, pelarasan terakhir dibuat ke bawah untuk memastikan keseluruhan pokok binari ialah akar yang besar (pelarasan ini terutamanya untuk pengisihan timbunan kemudian).

Proses pelarasan khusus adalah seperti berikut:

Cara melaksanakan ia dengan kod?

Kami mula-mula melaraskan daripada subpokok terakhir, kemudian kami perlu mendapatkan induk nod akar subpokok terakhir Kami tahu bahawa subskrip nod terakhir tatasusunan ialah len - 1, dan nod ini ialah subpokok terakhir. . Untuk anak kiri atau kanan pokok, anda boleh mendapatkan subskrip nod akar (induk) berdasarkan subskrip anak-- membenarkan setiap subpokok dilaraskan sehingga ia mencapai nod akar, dan kemudian melaraskan ke bawah untuk yang terakhir. masa, anda boleh mendapatkan timbunan akar yang besar.

// 将数组变成大根堆结构
public void createHeap(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        elem[i] = arr[i];// 放入elem[],假设不需要扩容
        usedSize++;
    }
    // 得到根节点parent, parent--依次来到每颗子树的根节点，
    for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
        // 依次向下搜索，使得每颗子树都变成大根堆
        shiftDown(parent,usedSize);
    }
}
// 向下搜索变成大根堆
public void shiftDown(int parent,int len){
    int child = parent*2+1;// 拿到左孩子
    while (child < len){
        // 如果有右孩子,比较左右孩子大小,得到较大的值和父节点比较 
        if (child+1 < len && (elem[child] < elem[child+1])){
            child++;
        }
        // 比较较大的孩子和父节点,看是否要交换
        int max = elem[parent] >= elem[child] ? parent : child;
        if (max == parent) break;// 如果不需要调整了，说明当前子树已经是大根堆了，直接 break
        swap(elem,parent,child);
        parent = child;// 继续向下检测，看是否要调整
        child = parent*2+1;
    }
}
public void swap(int[] arr,int i,int j){
  	int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Timbunan akar kecil (timbunan minimum)

Timbunan akar kecil memastikan bahawa nod akar setiap pokok binari adalah lebih kecil daripada bahagian kiri dan nod anak kanan

Proses pelarasan adalah sama seperti di atas.

Priority Queue (PriorityQueue)

Dalam java, struktur data timbunan (PriorityQueue) disediakan, juga dipanggil priority queue Apabila kita membuat sedemikian sesuatu objek, kita mendapat timbunan akar kecil tanpa data tambahan. timbunan.

// 默认得到一个小根堆
PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
smallHeap.offer(23);
smallHeap.offer(2);
smallHeap.offer(11);
System.out.println(smallHeap.poll());// 弹出2，剩余最小的元素就是11，会被调整到堆顶，下一次弹出
System.out.println(smallHeap.poll());// 弹出11

 // 如果需要得到大根堆，在里面传一个比较器
 PriorityQueue<Integer> BigHeap = new PriorityQueue<>(new Comparator<Integer>() {
     @Override
     public int compare(Integer o1, Integer o2) {
         return o2 - o1;
     }
 });

2. Idea untuk menyelesaikan masalah top-k

Contoh: Terdapat sekumpulan elemen dan anda diminta untuk mencari tiga elemen terkecil pertama.

Idea 1: Isih tatasusunan daripada kecil kepada besar dan dapatkan 3 elemen pertama tatasusunan. Walau bagaimanapun, boleh didapati bahawa kerumitan masa kaedah ini terlalu tinggi dan tidak digalakkan.

Idea 2: Letakkan semua elemen ke dalam struktur timbunan, dan kemudian timbulkan tiga elemen Elemen yang muncul setiap kali ialah elemen terkecil dalam timbunan semasa, kemudian tiga elemen yang muncul ialah tiga elemen terkecil pada masa lalu.

Idea ini boleh dilakukan, tetapi dengan mengandaikan saya mempunyai 1,000,000 elemen dan hanya muncul tiga elemen terkecil pertama, maka timbunan saiz 1,000,000 akan digunakan. Kerumitan ruang untuk melakukan ini adalah terlalu tinggi, jadi kaedah ini tidak disyorkan.

Tiga idea:

Kita perlu mendapatkan tiga elemen terkecil, kemudian membina timbunan dengan saiz 3. Anggapkan bahawa struktur timbunan semasa diisi dengan tepat 3 elemen, maka ini The tiga elemen ialah tiga elemen terkecil semasa. Dengan mengandaikan bahawa elemen keempat adalah salah satu elemen yang kita mahu, maka sekurang-kurangnya satu daripada tiga elemen pertama bukanlah yang kita mahu, dan ia perlu dimunculkan.

Apa yang kita mahu dapatkan ialah tiga elemen terkecil yang pertama, jadi elemen terbesar dalam struktur timbunan semasa mestilah tidak seperti yang kita mahu, jadi di sini kita membina timbunan akar yang besar. Pop elemen dan kemudian masukkan elemen keempat sehingga keseluruhan tatasusunan dilalui.

这样我们就得到了只含有前三个最小元素的堆，并且可以看到堆的大小一直都是3，而不是有多少数据就建多大的堆，然后再依次弹出元素就行了。

// 找前 k个最小的元素
public static int[] topK(int[] arr,int k){
     // 创建一个大小为 k的大根堆
     PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
         @Override
         public int compare(Integer o1, Integer o2) {
             return o2 - o1;
         }
     });
     for (int i = 0; i < arr.length; i++) {
         if (i < k){
             // 放入前 k 个元素
             maxHeap.offer(arr[i]);
         }else{
             // 从第 k+1个元素开始进行判断是否要入堆
             if (maxHeap.peek() > arr[i]){
                 maxHeap.poll();
                 maxHeap.offer(arr[i]);
             }
         }
     }
     int[] ret = new int[k];
     for (int i = 0; i < k; i++) {
         ret[i] = maxHeap.poll();
     }
     return ret;
 }

Atas ialah kandungan terperinci Bagaimana untuk menggunakan timbunan untuk menyelesaikan masalah Top-k di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!