Timbunan - Minimum dan Maks

Timbunan - Timbunan Min

Heap ialah versi senarai keutamaan yang lebih cekap. Ambil kira kaedah sisipan dan pengalihan bagi Barisan Keutamaan Diisih dan Tidak Diisih, dalam Kos sisipan Tidak Diisih O(1), mengalih keluar kos O(n), manakala kos memasukkan Diisih O(n) dan mengalih keluar O(1).

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

Heap dibina oleh Array, tetapi perwakilannya ialah pokok binari, elemen yang mempunyai keutamaan terbanyak adalah di bahagian atas, akar. Ia diisi dari atas ke bawah dan kanan ke kiri, tanpa kanak-kanak hilang!

?

Walau bagaimanapun, terdapat kemungkinan membina struktur data dengan keutamaan tertinggi ditakrifkan oleh nilai kunci tertinggi. Dalam kes ini, kita mempunyai timbunan maksimum, yang akan kita lihat kemudian.

Min_Heap

Untuk menjadi Heap yang sah, semua elemen kanak-kanak mesti mempunyai keutamaan yang lebih rendah atau sama daripada ibu bapa mereka. Tambahan pula, ia mesti lengkap tanpa kanak-kanak yang hilang, jika tidak tatasusunan akan mempunyai ruang kosong.

?

Cara yang lebih formal untuk melaksanakan definisi ini adalah dengan mengatakan bahawa pokok binari adalah lengkap jika tahapnya 0, 1, 2, · · · h − 1 mempunyai unsur maksimum yang mungkin dan unsur-unsur yang wujud pada tahap h diperuntukkan sejauh mungkin ke kiri.

Seperti yang dinyatakan, timbunan terdiri daripada tatasusunan (diwakili dalam warna hijau), tetapi boleh dilihat sebagai struktur pokok, seperti yang ditunjukkan dalam imej di bawah.

Terdapat dua cara untuk memasang Heap, dengan elemen pertama dalam kedudukan 0, atau tanpa kedudukan 0, dalam artikel ini kita akan melihat perbezaan antara kedua-dua kes tersebut. Elemen di bahagian atas sentiasa mempunyai anak mereka, biasanya dikenali sebagai elemen di bahagian bawah, untuk menemui kanak-kanak ini, dalam kes indeks 0, anda boleh mendapatkan maklumat ini menggunakan pengiraan ini:

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Jika anda menggunakan versi dengan 0 tidak diisi, cuma kurangkan jumlahnya, iaitu 1-1=0, dalam kes induk ia adalah indeks / 2.

Sisipkan

Ia sentiasa ditambah pada penghujung, satu-satunya kebimbangan yang anda perlu ada ialah apabila menyemak sama ada elemen anak mempunyai kunci yang lebih rendah daripada induk, untuk tujuan ini menggelegak dilakukan, iaitu apabila Kekunci elemen yang dimasukkan adalah berbanding dan bapa, menukar jika perlu.

Bercakap dengan lebih terperinci, letakkan elemen di ruang kosong terakhir pokok dan, kerana anda perlu membandingkan kuncinya dengan kunci induk, kita perlu mengira indeks induk untuk mengakses kuncinya. Untuk mengetahui bapa, gunakan pengiraan yang disebutkan:

parent = (indexDoFilho -1)/2

Dan untuk ini, indexDoFilho tiada: untuk mendapatkan ini, kami mengambil pembolehubah untuk menjadi indeks semasa, kerana kami berada dalam sisipan yang merupakan tambahan pada penghujung, indeks semasa adalah yang terakhir, iaitu:

currentIndex = size-1

Sekarang mempunyai indeks semasa, hubungi Ibu Bapa dan ketahui siapa bapa elemen yang dimasukkan. Kami mahukan induk elemen baharu ini kerana, untuk menyusun pokok dengan betul, elemen ini mesti dibandingkan dengan induknya dan, jika kuncinya lebih kecil, ia mesti bertukar lokasi.

Selagi indeks semasa lebih besar daripada 0 (untuk mengelak daripada mengambil indeks yang tidak tersedia) dan indeks semasa lebih kecil daripada indeks induk, jika keadaan ini benar, elemen tersebut perlu ditukar dengan induk untuk menjamin pemilikan timbunan minimum dan kemudian swap berlaku dan kemudian indeks semasa menerima indeks induk, dan kemudian mengambil induk induk (KKKKK) untuk . Swap ialah kaedah yang menggunakan struktur pertukaran nilai biasa.

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Berkaitan:

parent = (indexDoFilho -1)/2

Tukar sebagai kaedah biasa untuk menukar nilai:

currentIndex = size-1

Jika nilai elemen semasa (anak) kurang daripada nilai induk, ini menunjukkan bahawa sifat timbunan minimum telah dilanggar. Dalam timbunan minimum, ibu bapa mesti sentiasa kurang daripada atau sama dengan anak. Apabila syarat ini tidak dipenuhi, anak mesti bertukar tempat dengan ibu bapa supaya nilai yang lebih kecil terus "mendaki" dalam timbunan sehingga ia menemui kedudukan yang betul, di mana harta itu akan dikekalkan.

Alih keluar

Mengalih keluar elemen indeks 0, tetapi pokok itu tidak lagi lengkap! Untuk menyelesaikannya, tarik elemen terakhir tatasusunan ke permulaan, iaitu, elemen terakhir yang ditambahkan pergi ke bahagian atas pokok. Selepas itu, semak semula, tetapi sekarang dari atas ke bawah. Dengan kata lain, inilah masanya untuk membandingkan ibu bapa dengan anak-anak mereka! (tenggelam)
Kaedah sinkDown() mengalihkan elemen ke bawah (atau "tenggelam") dalam timbunan, sehingga ia berada dalam kedudukan yang betul, di mana nilainya adalah kurang daripada atau sama dengan nilai anak-anaknya (jika ia berada dalam kedudukan dengan kanak-kanak) .
Dalam sinkDown terdapat pembolehubah untuk menyimpan indeks elemen dengan kunci terendah bermula pada akar dan satu lagi untuk indeks semasa. Kemudian, gelung yang akan bertahan sehingga indeks elemen semasa adalah sama dengan indeks elemen dengan kunci terendah. Di dalam gelung, dapatkan kanak-kanak yang semasa dan lihat sama ada kanak-kanak itu berada dalam julat tatasusunan dan jika indeks kanak-kanak itu kurang daripada indeks minimum, ia mengemas kini minimum.

public void insert(K key, V value) { //o(log n)
    if (isFull()){
        throw new RuntimeException("full");
    }
    //adc a entry na ultima posição do vetor
    heap[size++]=new PriorityEntry(key, value);
    //guarda o index que esse novo elemento tá
    int currentIndex = size-1;
    //chama o método parent pra calcular quem é o pai do novo elemento
    int parent = parent(currentIndex);
    //percorre enquanto o index nao for o 0 e o index ser 
    while (currentIndex>0 && compare(currentIndex, parent)<0){
        swap(currentIndex, parent);
        currentIndex = parent;
        parent = parent(currentIndex);
    }
}

Dalam kes ini:

protected int parent(int index){
        return (index-1)/2;
}

Ringkasan:

Sifat Timbunan Min:

• Struktur pokok binari lengkap.
• Nod induk sentiasa mempunyai nilai yang sama atau kurang daripada nod anaknya.
• Dilaksanakan melalui tatasusunan, di mana kedudukan anak dan ibu bapa ditentukan oleh formula berdasarkan indeks.

Untuk mengira kedudukan anak dan ibu bapa:

• Kiri: leftChild = indeks * 2 1
• Kanan: kananKanak-kanak = indeks * 2 2
• Ibu bapa: ibu bapa = (indeks - 1) / 2

Versi tanpa indeks 0: Hanya tolak 1 daripada pengiraan, menghasilkan:

• leftChild = indeks * 2
• kananKanak = indeks * 2 1
• ibu bapa = indeks / 2

Timbunan - Timbunan Maks

Nilai tertinggi adalah pada akar, jadi nod induk mempunyai nilai yang sama atau lebih besar daripada anak-anaknya

Formula untuk mengira kanak-kanak dan ibu bapa:

• Kiri: leftChild = indeks * 2 1
• Kanan: kananKanak-kanak = indeks * 2 2
• Ibu bapa: ibu bapa = (indeks - 1) / 2

Sisipkan

Menambahkan elemen pada penghujung dan menggelegak, yang akan membandingkan elemen dengan induknya, menukar lokasi jika perlu. O(log n).

rigthChild = LeftChild + 1
//para saber o elemento da esquerda do pai
leftChild = indexDoFilho * 2 +1
//para saber qual o pai do elemento
parent = (indexDoFilho -1)/2

Alih keluar

Mengalih keluar elemen heapMax[0], aka akar, dan kemudian mengambil elemen terakhir dan menggerakkannya ke atas ke akar, memanggil sinkdown kemudian menolak elemen baharu daripada akar ke bawah sehingga ia menemui kedudukannya yang betul.

sinkDown perlu memastikan bahawa nilai dalam nod induk adalah lebih besar daripada atau sama dengan nilai dalam nod anak. Oleh itu, apabila menenggelamkan nod, ia akan dibandingkan dengan anak terbesar.

Dalam Min Timbunan, sinkDown mesti memastikan bahawa nilai dalam nod induk adalah kurang daripada atau sama dengan nilai kanak-kanak. Dalam kes ini, perbandingan dibuat dengan anak terkecil.

parent = (indexDoFilho -1)/2

currentIndex = size-1

Perbezaan

• Dalam Max Heap, sinkDown perlu memastikan bahawa nilai dalam nod induk adalah lebih besar daripada atau sama dengan nilai dalam nod anak. Oleh itu, apabila menenggelamkan nod, ia akan dibandingkan dengan anak terbesar.
• Dalam Max Heap, jika nod induk lebih kecil daripada anak terbesarnya, maka ia mesti bertukar dengan anak terbesar untuk memastikan nilai terbesar setinggi mungkin.
• Dalam Min Timbunan, sinkDown mesti memastikan bahawa nilai dalam nod induk adalah kurang daripada atau sama dengan nilai kanak-kanak. Dalam kes ini, perbandingan dibuat dengan anak terkecil.
• Dalam Tumpukan Min, penukaran berlaku jika nod induk lebih besar daripada anak terkecil, mengekalkan nilai terkecil di bahagian atas

Atas ialah kandungan terperinci Timbunan - Minimum dan Maks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!