Soalan
Laksanakan Fibonacci Heap yang menyokong insert, meld, find-min, extract-min, decrease-key, dan delete. Terangkan cara senarai punca, pautan ibu bapa-anak, darjah (degree), bit tanda (mark bit), dan pemotongan melata (cascading cuts) berfungsi bersama-sama, dan gunakan fungsi keupayaan untuk menunjukkan mengapa insert, meld, find-min, dan decrease-key adalah O(1) terlunas manakala extract-min adalah O(log n) terlunas.
Perkara yang diuji oleh penemu duga
- Sama ada anda membezakan kos sebenar daripada kos terlunas dan bukannya menyatakan setiap operasi terlunas O(1) sentiasa O(1).
- Sama ada anda mengekalkan senarai pautan berganda membulat (circular doubly linked lists), penuding punca minimum, pemegang nod (node handles), dan penuding ibu bapa.
- Sama ada decrease-key melakukan pemotongan, penandaan, dan pemotongan melata dengan betul.
- Sama ada anda boleh menerangkan kelebihan teori, pemalar kejuruteraan, dan pertukaran kompromi (trade-offs) berbanding pairing heap dan timbunan perduaan (binary heap).
Jawapan model
Fibonacci Heap ialah himpunan pokok tersusun timbunan (heap-ordered trees). Punca-punca membentuk senarai pautan berganda membulat, dan setiap nod menyimpan ibu bapa, senarai anak, darjah, dan bit tanda. Struktur ini menangguhkan penyatuan (consolidation) sehingga extract-min, apabila punca-punca dipautkan mengikut darjah.
insert menambah nod ke senarai punca dan mengemas kini nilai minimum; meld menyambungkan dua senarai punca. Jika decrease-key melanggar susunan timbunan, potong nod tersebut daripada ibu bapanya dan tambahkannya ke senarai punca. Jika ibu bapa telah kehilangan satu anak sebelum ini, lakukan pemotongan melata secara rekursif. Tanda merekodkan sama ada nod telah kehilangan satu anak dan mengehadkan kerosakan melata.
extract-min menaikkan anak-anak punca minimum ke senarai punca, mengalih keluar punca tersebut, dan memautkan punca-punca yang mempunyai darjah yang sama secara berulang kali. Keupayaan umum ialah bilangan punca ditambah dua kali ganda bilangan nod bertanda. Insert dan meld meningkatkan punca tetapi hanya membayar kos pemalar; pemotongan melata mengurangkan nod bertanda dan dibayar oleh keupayaan. Bilangan pautan dalam extract-min dibatasi oleh O(log n) kerana susunan timbunan mengehadkan darjah maksimum.
Lakaran pelaksanaan
Kod pseudo menunjukkan laluan kritikal decrease-key; pemanggil memegang pemegang nod.
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)Semasa extract-min, simpan penuding seterusnya dengan selamat semasa menaikkan anak-anak sebelum mengalih keluar punca minimum. Memautkan punca berdarjah sama mesti mengemas kini ibu bapa, anak, darjah, dan tanda, diikuti dengan imbasan untuk mencari minimum baharu.
Perangkap lazim
- Menulis timbunan perduaan berasaskan tatasusunan dan mendakwa ia mempunyai O(1) terlunas decrease-key Fibonacci Heap.
- Terlupa untuk mengosongkan ibu bapa atau tanda selepas pemotongan, sekali gus merosakkan lata seterusnya.
- Memadam daripada senarai pautan berganda membulat semasa menggunakan penuding seterusnya yang tidak sah.
- Hanya membandingkan punca lama selepas extract-min dan terlupa anak-anak yang dinaikkan dalam senarai punca dan imbasan minimum.
- Hanya membandingkan batas asimptotik sambil mengabaikan penjejakan penuding (pointer chasing), lokaliti cache, peruntukan memori, dan kerumitan pelaksanaan.
Pertukaran kompromi kerumitan
Apabila decrease-key kerap digunakan, meld diperlukan, dan analisis terlunas boleh diterima, Fibonacci Heap mempunyai batas teori yang menarik; contoh klasik ialah batas yang dipertingkatkan untuk algoritma Prim dan Dijkstra. Dalam persekitaran pengeluaran, pairing heap, rank-pairing heap, atau timbunan perduaan sering bersaing dengan lebih baik kerana ia lebih ringkas dan lebih mesra cache.
Batas ini mengandaikan adanya pemegang nod. Jika pemanggil hanya boleh mencari nod mengikut kunci, indeks bantuan akan mengubah reka bentuk. Pelaksanaan serentak juga mesti mentakrifkan pemilikan senarai punca dan pemegang; keselamatan bebas kunci (lock-free) tidak terhasil secara automatik daripada analisis terlunas.
Uji kes nod tunggal (singleton), kunci pendua, meld dengan timbunan kosong, decrease-key berulang, dan memadamkan nod terakhir. Jana jujukan operasi rawak dan bandingkan nilai minimum serta susunan extract-min dengan baris gilir keutamaan rujukan. Bina nod yang kehilangan dua anak berturut-turut untuk mengesahkan bahawa kehilangan pertama menandakannya dan kehilangan kedua memotongnya.
Rujukan
- Syarahan Fibonacci heaps MIT OpenCourseWare: analisis keupayaan dan batas decrease-key/extract-min.
- Fibonacci Heaps Revisited: analisis semula pemotongan melata dan batas terlunas.
- Kertas asal Fredman dan Tarjan: Fibonacci heaps dan kegunaannya dalam algoritma pengoptimuman rangkaian.
Soalan susulan
Mengapakah nod bertanda menyumbang dua unit kepada fungsi keupayaan?
Pemotongan melata mengalih keluar satu nod bertanda dan menambah satu punca. Dua unit keupayaan membayar untuk mengosongkan tanda dan menambah punca, mengekalkan kos terlunas bagi keseluruhan lata sebagai pemalar.
Mengapakah extract-min adalah O(log n) terlunas?
Selepas mengalih keluar minimum dan menaikkan anak-anaknya, penyatuan mengekalkan paling banyak satu punca bagi setiap darjah. Susunan timbunan mengikat darjah nod dengan saiz subpokoknya, jadi darjah maksimum ialah O(log n), yang mengehadkan bilangan pautan.
Mengapakah meld boleh menjadi O(1) terlunas?
Dua senarai punca membulat boleh disambungkan secara terus dan penuding minimumnya dibandingkan. Pokok-pokok berdarjah sama tidak disatukan sehingga extract-min berikutnya.
Bilakah timbunan perduaan merupakan pilihan yang lebih baik?
Gunakan timbunan perduaan apabila decrease-key jarang berlaku, lokaliti tatasusunan adalah penting, pemegang nod menyusahkan, atau pasukan mengutamakan pelaksanaan yang lebih ringkas. Ia menyediakan operasi O(log n) dengan tingkah laku memori yang boleh diramal.
Bagaimanakah anda melaksanakan delete?
Turunkan kunci nod kepada infiniti negatif dan panggil extract-min. Pelaksanaan pengeluaran mesti mentakrifkan domain kunci, tingkah laku sentinela, dan pembatalan pemegang supaya kunci perniagaan yang sah tidak akan disalah anggap sebagai sentinela.