Pengenalan kepada senario aplikasi dan kaedah pelaksanaan timbunan Java

1. Penciptaan timbunan

1 Laraskan ke bawah (ambil timbunan kecil sebagai contoh)

Biar ibu bapa menandakan nod yang perlu dilaraskan, dan anak menandakan sebelah kiri anak kepada ibu bapa (nota: ibu bapa Jika ada anak, mesti ada anak kiri dahulu)

Jika anak kiri ibu bapa wujud, iaitu: saiz anak

• Sama ada anak kanan ibu bapa wujud, cari anak terkecil di antara anak kiri dan kanan, dan biarkan anak itu menandakannya

• Bandingkan ibu bapa dengan anak yang lebih kecil, jika:

Ibu bapa lebih kecil daripada anak yang lebih kecil, pelarasan selesai sebaliknya: tukar ibu bapa dengan anak yang lebih kecil , selepas swap selesai, elemen yang lebih besar dalam induk bergerak ke bawah, yang mungkin menyebabkan subpokok tidak memenuhi sifat timbunan, jadi kita perlu terus menyesuaikan ke bawah, iaitu, ibu bapa = anak = ibu bapa*2 +1; dan kemudian teruskan dengan 2.

public void shiftDown(int[] elem,int parent,int len){
        int cur=parent*2+1;
        while(cur<len){
           if(cur+1<len){
               if(elem[cur+1]<elem[cur]){
                   cur++;
               }
           }
            if(this.elem[cur]<this.elem[parent]) {
                swap(cur, parent);
            }
            parent=cur;
            cur=parent*2+1;
        }
    }

2. Buat timbunan

Untuk jujukan biasa, kita perlu mula melaraskan daripada nod induk pertamanya dengan nod kiri sehingga keseluruhan pokok memenuhi sifat timbunan.

3. Kerumitan masa mencipta timbunan

Timbunan mestilah pokok binari yang lengkap, dan pokok binari penuh juga merupakan pokok binari yang lengkap. Mengikut pengiraan berikut, kerumitan masa untuk mencipta timbunan ialah O(n).

2. Sisipan timbunan dan pemadaman

1

• Letakkan elemen yang hendak dimasukkan di hujung timbunan Jika ia tidak boleh diletakkan, kembangkannya

• Laraskan nod yang baru dimasukkan. ke atas sehingga ia berpuas hati Sifat timbunan

[Pelarasan ke atas]

public void shiftUp(int elem[],int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

2. Pemadaman timbunan

Mengikut timbunan Sifat pemadaman mestilah unsur teratas timbunan. Langkah-langkahnya adalah seperti berikut:

• Tukar elemen atas timbunan dengan elemen terakhir

• Bilangan unsur dalam timbunan dikurangkan oleh satu

• Laraskan elemen atas timbunan ke bawah

3. Penggunaan timbunan

1. Isih timbunan

Tertib menaik: Buat timbunan akar yang besar

Tertib menurun: Buat timbunan akar kecil

Tukar elemen atas timbunan dan elemen terakhir timbunan, dan laraskan ke bawah sehingga timbunan itu teratur.

2. Masalah atas-k [Cari nombor K terkecil]

Masalah atas-k: Cari nombor besar atau kecil k teratas dalam data set Elemen umumnya mempunyai jumlah data yang agak besar.

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array=new int[k];
        if(arr==null||arr.length<=k||k==0){
            return array;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        for(;i<k;++i){
            queue.offer(arr[i]);
        }
        while(i<arr.length){
            if(arr[i]<queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
            i++;
        }
        int size=queue.size();
        for(int j=0;j<size;++j){
            array[j]=queue.poll();
        }
        return array;
    }
}

4. Pengenalan antara muka biasa

1 Ciri-ciri PriorityQueue

PriorityQueue dan PriorityBlockingQueue disediakan dalam koleksi Java. rangka kerja Dua jenis barisan keutamaan. PriorityQueue adalah thread-unsafe, dan PriorityBlockingQueue adalah thread-safe. Artikel ini terutamanya memperkenalkan PriorityQueue.

Nota tentang penggunaan [PriorityQueue]:

• mesti mengimport pakej PeioriryQueue; Bandingkan saiz, jika tidak, ClassCastException akan dilemparkan; banyak seperti yang anda mahukan Elemen akan dikembangkan secara dalaman secara automatik;

• menggunakan struktur data timbunan di bahagian bawah, dan lalai ialah timbunan kecil. Jika anda ingin membina timbunan yang besar, anda perlu menyediakan pembanding.

• Kaedah pengembangan PriorityQueue:

• Jika kapasiti kurang daripada 64, ia dikembangkan sebanyak 2 kali ganda Kapasiti lama

• Jika kapasiti lebih besar daripada atau bersamaan dengan 64, kapasiti dikembangkan mengikut 1.5 kali Kapasiti lama

Jika kapasiti melebihi MAX_ARRAY_SIZE, kapasiti dikembangkan mengikut kepada MAX_ARRAY_SIZE

• int newCapacity = oldCapacity + ((oldCapacity < 64) ? ity >> 1));

• PriorityQueue dua kaedah: Comparble dan Comparator.

1. Comparble ialah kaedah perbandingan dalaman lalai Jika pengguna memasukkan objek jenis tersuai, objek mesti melaksanakan antara muka Comparble dan mengatasi kaedah compareTo

• 2 pilih untuk menggunakan objek pembanding, jika pengguna memasukkan objek jenis tersuai, anda mesti menyediakan kelas pembanding yang melaksanakan antara muka Pembanding dan mengatasi kaedah bandingkan

  // 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
  class IntCmp implements Comparator<Integer>{
     @Override
     public int compare(Integer o1, Integer o2) {
        return o2-o1;
     }
  }
  PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

  2、优先级队列的构造

  构造器	功能介绍
  PriorityQueue()	创建一个空的优先级队列，默认容量是11
  PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常
  PriorityQueue(Collection extends E> c)	用一个集合来创建优先级队列

  Atas ialah kandungan terperinci Pengenalan kepada senario aplikasi dan kaedah pelaksanaan timbunan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!