Pertanyaan
Implementasikan Fibonacci Heap yang mendukung insert, meld, find-min, extract-min, decrease-key, dan delete. Jelaskan bagaimana daftar akar (root list), relasi induk-anak (parent-child), derajat (degree), bit tanda (mark bit), dan pemotongan beruntun (cascading cut) bekerja bersama, serta gunakan fungsi potensial untuk menunjukkan mengapa insert, meld, find-min, dan decrease-key berukuran O(1) teramortisasi sementara extract-min berukuran O(log n) teramortisasi.
Apa yang diuji oleh pewawancara
- Apakah Anda membedakan biaya aktual dari biaya teramortisasi alih-alih mengatakan setiap operasi O(1) teramortisasi selalu berupa O(1).
- Apakah Anda mengelola circular doubly linked list, pointer minimum-root, handle simpul, dan pointer induk dengan benar.
- Apakah decrease-key melakukan pemotongan (cut), penandaan (marking), dan cascading cut secara tepat.
- Apakah Anda dapat menjelaskan keunggulan teoretis, konstanta rekayasa (engineering constants), dan pertukaran (trade-off) dibandingkan pairing heap dan binary heap.
Jawaban model
Fibonacci Heap adalah kumpulan pohon berurutan heap (heap-ordered trees). Simpul akar membentuk circular doubly linked list, dan setiap simpul menyimpan pointer induk, daftar anak, derajat, dan bit tanda. Struktur ini menunda konsolidasi hingga operasi extract-min dijalankan, yaitu ketika akar-akar digabungkan berdasarkan derajatnya.
insert menambahkan simpul ke daftar akar dan memperbarui nilai minimum; meld menggabungkan dua daftar akar. Jika decrease-key melanggar aturan urutan heap, potong simpul tersebut dari induknya dan tambahkan ke daftar akar. Jika induknya sudah pernah kehilangan satu anak, lakukan cascading cut secara rekursif. Tanda (mark) mencatat apakah suatu simpul telah kehilangan satu anak dan membatasi dampak beruntun.
extract-min menaikkan anak-anak dari akar minimum ke daftar akar, menghapus akar tersebut, dan secara berulang menghubungkan akar-akar dengan derajat yang sama. Fungsi potensial yang umum digunakan adalah jumlah akar ditambah dua kali jumlah simpul yang ditandai. Insert dan meld menambah akar tetapi hanya memerlukan biaya konstan; cascading cut mengurangi simpul yang ditandai dan biayanya ditanggung oleh potensial. Jumlah penggabungan dalam extract-min dibatasi oleh O(log n) karena aturan urutan heap membatasi derajat maksimum.
Sketsa implementasi
Pseudocode berikut menunjukkan alur kritis decrease-key; pemanggil memegang handle simpul.
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)Selama extract-min, simpan pointer next secara aman saat menaikkan anak-anak sebelum menghapus akar minimum. Penggabungan akar-akar berderajat sama harus memperbarui induk, anak, derajat, dan tanda, diikuti dengan pemindaian untuk mencari nilai minimum yang baru.
Jebakan umum
- Menulis binary heap berbasis array dan mengklaim bahwa heap tersebut memiliki decrease-key O(1) teramortisasi seperti Fibonacci Heap.
- Lupa membersihkan pointer induk atau tanda setelah pemotongan, yang merusak cascade berikutnya.
- Menghapus dari circular doubly linked list saat menggunakan pointer next yang tidak valid.
- Hanya membandingkan akar-akar lama setelah extract-min dan melupakan anak-anak yang dinaikkan ke daftar akar serta pemindaian minimum.
- Hanya membandingkan batas asimtotik tanpa memperhitungkan pointer chasing, lokalitas cache, alokasi memori, dan kompleksitas implementasi.
Pertukaran kompleksitas
Ketika decrease-key sering digunakan, meld diperlukan, dan analisis teramortisasi dapat diterima, Fibonacci Heap memiliki batas teoretis yang menarik; contoh klasiknya adalah perbaikan batas kompleksitas untuk algoritma Prim dan Dijkstra. Dalam sistem produksi, pairing heap, rank-pairing heap, atau binary heap sering kali bersaing lebih baik karena lebih sederhana dan lebih ramah terhadap cache.
Batas-batas ini mengasumsikan keberadaan handle simpul. Jika pemanggil hanya dapat mencari simpul berdasarkan kunci, indeks tambahan akan mengubah desain tersebut. Implementasi konkuren juga harus mendefinisikan kepemilikan daftar akar dan handle; keamanan bebas kunci (lock-free safety) tidak serta-merta didapat dari analisis teramortisasi.
Ujilah kasus dengan satu elemen (singleton), kunci duplikat, meld dengan heap kosong, decrease-key berulang, dan penghapusan simpul terakhir. Buat urutan operasi acak lalu bandingkan nilai minimum dan urutan extract-min dengan priority queue referensi. Buat simpul yang kehilangan dua anak secara berurutan untuk memverifikasi bahwa kehilangan pertama menandainya dan kehilangan kedua memotongnya.
Referensi
- Kuliah Fibonacci heaps MIT OpenCourseWare: analisis potensial dan batas decrease-key/extract-min.
- Fibonacci Heaps Revisited: analisis ulang cascading cut dan batas teramortisasi.
- Makalah asli Fredman dan Tarjan: Fibonacci heaps dan penggunaannya dalam algoritma optimasi jaringan.
Pertanyaan lanjutan
Mengapa simpul yang ditandai menyumbang dua unit ke fungsi potensial?
Cascading cut menghapus satu simpul yang ditandai dan menambahkan satu akar. Dua unit potensial membayar biaya pembersihan tanda dan penambahan akar, menjaga biaya teramortisasi dari seluruh rangkaian cascade tetap konstan.
Mengapa extract-min berukuran O(log n) teramortisasi?
Setelah menghapus elemen minimum dan menaikkan anak-anaknya, konsolidasi menyisakan paling banyak satu akar per derajat. Aturan urutan heap mengikat derajat simpul dengan ukuran subpohonnya, sehingga derajat maksimum adalah O(log n), yang membatasi jumlah penggabungan link.
Mengapa meld dapat berukuran O(1) teramortisasi?
Dua circular root list dapat digabungkan secara langsung dan pointer minimum keduanya dapat langsung dibandingkan. Pohon-pohon dengan derajat yang sama tidak dikonsolidasi hingga extract-min berikutnya dijalankan.
Kapan binary heap menjadi pilihan yang lebih baik?
Gunakan binary heap ketika decrease-key jarang dilakukan, lokalitas array penting, handle simpul tidak praktis digunakan, atau tim mengutamakan implementasi yang lebih sederhana. Binary heap menyediakan operasi O(log n) dengan perilaku memori yang mudah diprediksi.
Bagaimana Anda mengimplementasikan delete?
Turunkan kunci simpul menjadi minus tak hingga lalu panggil extract-min. Implementasi produksi harus mendefinisikan domain kunci, perilaku sentinel, dan pembatalan handle (handle invalidation) agar kunci bisnis yang valid tidak pernah disalahartikan sebagai sentinel.