Barisan Keutamaan! Mari kita pecahkan dan pelajari tentang bahagian Struktur Data ini.

Beratur

Baris gilir, seperti Tindanan, ialah pengkhususan Senarai. Ia berdasarkan asas FIFO - masuk pertama, keluar dahulu, yang bermaksud bahawa masuk pertama ialah keluar pertama. Dalam erti kata lain, orang "tertua" dalam baris gilir keluar dahulu, untuk pemahaman yang lebih baik, pertimbangkan baris gilir bank.

⚠️

Aplikasi Beratur: Pengurusan proses dalam sistem pengendalian; Komunikasi antara tugas dalam pengaturcaraan serentak; rangkaian komputer (pencetakan); respons kepada permintaan pada pelayan Web

Baris gilir itu sendiri hanya membenarkan manipulasi langsung data di hujungnya.

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

Barisan Keutamaan

Ia menyerupai gelagat baris gilir biasa, tetapi kini pertimbangkan bahawa anda berada dalam barisan di bank dan seorang wanita memasuki baris gilir, semua orang membiarkan dia meneruskannya kerana dia mempunyai KEUTAMAAN yang lebih besar kerana dia semakin tua.

Dalam Struktur Data Gilir Keutamaan, setiap nod mempunyai Key-Value, Key ialah kunci yang menyimpan keutamaannya, Value ialah nilai nod. Secara lalai Java, Kunci pada mulanya adalah angka dan boleh diubah oleh pengaturcara kemudian.

Set Kunci dan Nilai dipanggil Entri, jadi antara muka E.D ini berubah. Butiran lain ialah: selepas Kunci ditakrifkan, ia tidak boleh diubah. Jika dua nod mempunyai nilai keutamaan yang sama dalam Kunci, pengaturcara memilih peraturan.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

Dalam struktur seterusnya, kami akan menggunakan kelas untuk Nod dan Entry, atribut pertama, terakhir dan saiz, dan compareTo

Baris gilir keutamaan terbahagi kepada dua: yang diisih (Baris Keutamaan Diisih) dan yang tidak diisih (Baris Keutamaan Tidak Diisih)

Barisan Keutamaan Isih

Senarai tersusun menguruskan memasukkan nod pada kedudukan yang betul, jadi pengalihan keluar adalah mudah, cuma keluarkan yang pertama (jika pengaturcara melakukan E.D mentakrifkan bahawa elemen keutamaan tertinggi harus berada di permulaan)

Untuk mengetahui nod mana yang mempunyai keutamaan tertinggi, kami menggunakan compareTo, fungsi Collections yang, melalui pengembaliannya, kami boleh memperoleh hasil penting untuk pelaksanaan E.D ini, jika pulangan ialah:

• Negatif: Jika objek yang memanggil kaedah adalah "lebih kecil" daripada objek yang diluluskan sebagai parameter.
• Sifar: Jika objek adalah sama.
• Positif: Jika objek yang memanggil kaedah adalah "lebih besar" daripada objek yang diluluskan sebagai parameter.

Sisipkan

Untuk masuk anda mesti menyemak beberapa perkara

Langkah pertama → Cipta nod baharu

Node newNode = new Node(key, value)

Langkah ke-2 → Semak jika Baris kosong, jika ya, letakkan Head dan Last sebagai nod baharu, memandangkan ia akan menjadi satu-satunya

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

Langkah ke-3 → Jika ia bukan satu-satunya elemen dalam senarai, anda mesti menyemak sama ada nod baharu, berbanding dengan yang pertama, mempunyai keutamaan yang lebih tinggi atau tidak.

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

Langkah ke-3 → Kemudian bandingkan dengan elemen terakhir dalam senarai

Node newNode = new Node(key, value)

Langkah ke-4 → Jika tidak semua yang lain, hanya tinggal bahagian tengah! Untuk melakukan ini, kita perlu membuat nod tambahan untuk pergi ke hadapan newNode (nN) dan membandingkan kedua-duanya, perbandingan berakhir apabila auxNode menunjuk kepada tiada, atau apabila nN lebih besar daripada auxNode (lebih besar, jadi ia berada di belakang dalam barisan). Sewaktu ini digunakan untuk aux berputar dan membandingkan nilai dua nod, apabila ia menemuinya, ia meletakkan nN di belakang auxNode

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

Alih keluar

Kaedah alih keluar dalam Diisih adalah lebih mudah kerana, seperti yang telah disebutkan, Baris Gilir sudah diatur untuknya.

Langkah pertama → Memandangkan setiap kaedah Alih Keluar mengembalikan elemen yang akan dialih keluar, langkahnya adalah untuk mencipta Entri (Mengapa bukan nod?)

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

Langkah ke-2 → Kemudian, kerana anda sudah akan menghapuskan nod pertama, hanya tunjuk Pertama kepada yang di sebelah Pertama

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

Langkah ke-3 → Semak sama ada terdapat hanya satu elemen dalam Baris, kerana jika ya, Baris Gilir akan kosong! Kemudian anda perlu menetapkan F dan L kepada null

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

Langkah ke-4 → Jika ia bukan satu-satunya elemen, ini bermakna ada yang lain! Jadi, apabila anda mengalih keluar yang pertama dalam langkah 2, perkara yang dahulunya Pertama masih disambungkan oleh yang sebelumnya, jadi kita mesti:

        Entry<K,V> max = maxPriority();

MaxPriority

Kaedah yang mengembalikan elemen keutamaan tertinggi dalam senarai, dan memandangkan kami teratur, ia hanya mengembalikan elemen yang pertama.

        first = first.next;

Analisis Asymptotic

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

Baris Keutamaan Tidak Isih

Barisan yang tidak teratur sangat berbeza daripada yang dipesan! Jom mulakan dengan kaedah beliau:

Sisipkan

Untuk menambah pada yang tidak diisih, suka dan tidak teratur, anda tidak perlu risau tentang di mana elemen baharu ini akan berada, cuma tambahkannya pada penghujungnya!

Langkah pertama → Semak sama ada senarai itu kosong, kerana jika ya, nod yang akan ditambah adalah yang pertama (Pertama) dan yang terakhir (Terakhir)

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

Langkah ke-2 → jika ia tidak kosong, cuma bimbang tentang menambah nod ini pada penghujung!

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

MaxPriority

Alih keluar dalam Unsorted jauh lebih kompleks daripada baris kod yang sedikit dalam Sorted…

“Kenapa?” anda bertanya, kami harus menggunakan kaedah (yang dalam versi lain juga lebih mudah) dipanggil maxPriority, yang objektifnya adalah untuk mencari nod dengan keutamaan tertinggi. Sebelum ini ia diajar dengan cara yang mudah dengan hanya beberapa baris kod, sekarang, kerana kita tidak tahu di mana nod keutamaan tertinggi ini sebenarnya, kita mesti melalui keseluruhan baris gilir untuk mencarinya! Jadi sebelum kita melihat pada remove itself, kita akan melihat pada maxPriority.

Langkah pertama → Setiap kali kita ingin melintasi struktur data, kita memerlukan dua nod: satu nod tambahan untuk sentiasa meneruskan dan yang ingin kita capai (dalam kes ini ialah MaxPriority)

Node newNode = new Node(key, value)

Langkah ke-2 → Kedua-dua ini akan berjalan dalam satu nod, ia hanya tamat apabila aux mencapai null (hujung baris gilir). Bandingkan nod ini dan jika ia negatif, ini bermakna aux lebih kecil daripada maks, jadi max adalah yang terbesar, mengemas kini nilai Nod maks, dan kemudian menjadikan aux dijalankan.

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

Alih keluar

Langkah pertama → Dalam semua emove, buat pembolehubah yang akan menyimpan nod yang akan dialih keluar. Dalam kes ini, anda sudah tahu yang mana satu akan dialih keluar kerana anda memanggil kaedah maxPriority

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

Langkah ke-2 → Kemudian semak sama ada ia adalah satu-satunya elemen, jika ya, F dan L adalah batal!

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

Langkah ke-3 → Jika ia bukan satu-satunya, terdapat pilihan lain: jika maks adalah yang terakhir, hapuskan yang terakhir, jika ia yang pertama, hapuskan yang pertama, jika ia bukan dua dua, ia dalam tengah!

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

Langkah ke-4 → Jika ia berada di tengah-tengah, maksimum yang terdapat dalam orang ramai perlu dialih keluar, ini berlaku apabila tiada orang lain yang menunjuk kepadanya.

        Entry<K,V> max = maxPriority();

Analisis Asymptotic

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(1)
remove	O(n)
maxPriority	O(n)

Atas ialah kandungan terperinci Barisan Keutamaan! Mari kita pecahkan dan pelajari tentang bahagian Struktur Data ini.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!