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.
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.
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;
}
Sifat Timbunan Min:
Untuk mengira kedudukan anak dan ibu bapa:
Versi tanpa indeks 0: Hanya tolak 1 daripada pengiraan, menghasilkan:
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:
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
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
Atas ialah kandungan terperinci Timbunan - Minimum dan Maks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Cara membuat pautan lembut
Kaedah pendaftaran akaun Google
tetapan pembolehubah persekitaran java
Perkara yang perlu dilakukan jika chrome tidak dapat memuatkan pemalam
Bagaimana untuk memulihkan sejarah penyemak imbas pada komputer
padam folder dalam linux
arahan pengguna suis linux
Kedudukan sepuluh pertukaran mata wang digital teratas
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
