Permintaan dan konteks
Implementasikan meldable min-priority queue untuk penjadwal acara yang prioritas tugasnya dapat menurun. Binary heap menangani operasi dasar, tetapi meld dan decrease-key menambah biaya komputasi. Implementasikan pairing heap dengan handle, penautan (linking), penggabungan dua lintasan (two-pass merging), penghapusan, dan kasus-kasus khusus.
Pairing heap diperkenalkan pada tahun 1986 sebagai self-adjusting heap yang bertujuan untuk menggabungkan implementasi sederhana dengan performa praktis yang baik; makalah aslinya hanya memberikan analisis kompleksitas parsial. Wawancara ini menguji apakah Anda memisahkan kebenaran kode, penalaran teramortisasi, dan klaim kompleksitas yang belum terbukti.
Apa yang dievaluasi pewawancara
Cakup invarian min-heap, meld waktu konstan, two-pass sibling pairing, stale handle, cut-and-relink decrease-key, key kosong dan duplikat, kepemilikan memori, serta pertukaran (trade-off) terhadap binary heap dan Fibonacci heap.
Pertanyaan klarifikasi untuk diajukan
- Apakah decrease-key diperlukan, atau hanya push/pop, dan bagaimana komposisi operasinya?
- Haruskah node handle tetap stabil, dan bagaimana stale handle dideteksi?
- Apakah rekursi diperbolehkan, dan berapa ukuran heap maksimum serta batasan tumpukan (stack budget)?
- Bisakah komparator melempar exception atau berubah, dan apakah prioritas duplikat didukung?
- Apakah tujuannya adalah kejelasan edukatif, kecepatan praktis dengan konstanta rendah, atau bukti kasus terburuk yang ketat?
Jawaban 30 detik
“Setiap node menyimpan key, payload, parent, first child, dan next sibling, dengan handle yang menunjuk ke node tersebut. Link membandingkan dua root dan menjadikan root yang lebih besar sebagai first child dari root yang lebih kecil. Delete-min melepaskan root, menautkan sibling dari kiri ke kanan secara berpasangan, lalu menggabungkannya dari kanan ke kiri. Decrease-key memotong node non-root dan menggabungkannya (meld) sebagai root. Lacak status handle dan jelaskan kompleksitas menggunakan analisis teramortisasi serta analisis yang telah mapan.”
Pembahasan mendalam langkah demi langkah
Langkah 1: Mendefinisikan node dan handle
Simpan key, payload, parent, first child, dan right sibling di setiap node. Sebuah handle menunjuk ke node dan membawa penanda aktif (live marker) atau generasi, mencegah decrease-key setelah penghapusan. Root tidak memiliki parent dan ujung dari sibling list bernilai null.
Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }Komparator hanya mengurutkan nilai dan tidak memutasi node. Perlakukan key yang sama sebagai node yang berbeda dan terapkan kebijakan stabilitas yang diperlukan.
Langkah 2: Mengimplementasikan link dan meld
link(a, b) membandingkan dua root, menjadikan root dengan key lebih besar sebagai first child dari root dengan key lebih kecil, dan memperbarui pointer parent serta sibling. meld hanya menautkan dua root; heap yang kosong akan mengembalikan root lainnya.
Setelah setiap pembaruan pointer, pastikan (assert) bahwa root tidak memiliki parent, setiap child menunjuk kembali ke parent-nya, dan ukuran tidak berubah. Build debug dapat menelusuri struktur untuk memeriksa siklus, tetapi operasi produksi tidak boleh melakukan pemeriksaan linier setiap saat.
Langkah 3: Mengimplementasikan insert dan find-min
insert membuat singleton heap, menggabungkannya (meld) dengan root, dan mengembalikan handle yang stabil. find-min membaca root; heap yang kosong mengembalikan hasil kosong atau error dari API alih-alih melakukan dereferensi null.
Jika pemanggil menyimpan handle, memindahkan atau memperbesar heap tidak boleh membatalkannya. Alokasikan node secara independen atau gunakan lapisan indireksi yang stabil, dan dokumentasikan apakah heap memiliki node tersebut atau hanya payload-nya.
Langkah 4: Mengimplementasikan two-pass delete-min
Setelah menghapus root, lepaskan child list-nya menjadi daftar root. Pada lintasan pertama, tautkan root yang berdekatan dari kiri ke kanan secara berpasangan; pertahankan root terakhir jika jumlahnya ganjil. Pada lintasan kedua, gabungkan (meld) hasilnya dari kanan ke kiri.
deleteMin(h):
children = detachChildren(h.root)
pairs = linkAdjacent(children)
newRoot = mergeRightToLeft(pairs)
invalidate(h.root)
h.root = newRoot
h.size -= 1Bersihkan pointer parent dan sibling yang lama selama penggabungan agar root yang dihapus tidak dipertahankan. Gunakan daftar iteratif untuk rantai sibling yang panjang guna menghindari stack overflow.
Langkah 5: Mengimplementasikan decrease-key
Tolak key baru yang tidak lebih kecil, atau tentukan operasi increase-key terpisah. Untuk root, perbarui key saja. Untuk non-root, potong dari child list parent-nya, perbaiki pointer sibling, dan gabungkan (meld) sebagai root independen.
Pemotongan membutuhkan sibling sebelumnya: pindai list parent, atau tambahkan pointer prevSibling dan terima pemeliharaan tambahan. Kembalikan error untuk handle yang usang (stale), node dari heap lain, atau heap yang telah dihancurkan.
Langkah 6: Menguji invarian dan kompleksitas
Gunakan pengujian diferensial acak terhadap priority queue standar, yang mencakup key duplikat, heap kosong, decrease-key berulang, penghapusan setiap node, dan meld acak. Setelah setiap operasi, verifikasi bahwa root bernilai minimal, ukuran cocok dengan node aktif, dan tautan parent-child bersifat asiklik.
Pisahkan batas yang terbukti, intuisi teramortisasi, dan hasil pengukuran. Insert dan meld pada pairing heap memiliki konstanta kecil, tetapi analisis ketat untuk delete-min dan decrease-key bukanlah alasan untuk mengklaim bahwa setiap operasi memiliki batas kasus terburuk O(log n). Nyatakan asumsi dan bandingkan dengan binary heap dan Fibonacci heap.
Contoh jawaban yang kuat
Saya akan menggunakan pointer parent, first-child, next-sibling, dan handle yang stabil untuk link, meld, two-pass delete-min, dan decrease-key. Operasi decrease-key pada non-root dipotong dari sibling list-nya sebelum digabungkan (meld) sebagai root baru; delete-min memasangkan dari kiri ke kanan dan menggabungkan dari kanan ke kiri. Saya akan melakukan uji diferensial terhadap priority queue standar, memeriksa invarian asiklisitas dan ukuran, serta membedakan analisis teramortisasi, batas kasus terburuk, dan tolok ukur praktis.
Kesalahan umum
- Hanya mengubah key → urutan heap dan tautan parent rusak → potong dan gabungkan (meld) setiap decrease-key non-root.
- Membalikkan urutan dua lintasan → bentuk dan hasil menjadi salah → pasangkan dari kiri ke kanan, lalu gabungkan dari kanan ke kiri.
- Menggunakan handle yang sudah dihapus → use-after-free atau mutasi lintas heap → batalkan validitas dan verifikasi kepemilikan.
- Mengklaim setiap operasi adalah kasus terburuk O(log n) → kompleksitas tidak memiliki dasar bukti → pisahkan analisis teramortisasi, analisis parsial, dan pengukuran.
- Melakukan rekursi melalui sibling list yang panjang → stack overflow → gunakan daftar iteratif.
Pertanyaan lanjutan dan tanggapan
Pertanyaan lanjutan 1: Mengapa tidak menggunakan binary heap secara langsung?
Binary heap memiliki tata letak array yang sederhana dan batasan performa yang stabil; pairing heap mungkin memiliki konstanta yang lebih kecil dengan meld dan decrease-key yang sering. Pilih berdasarkan komposisi operasi, lokalitas memori, dan persyaratan pembuktian.
Pertanyaan lanjutan 2: Bagaimana decrease-key dapat menghindari pemindaian sibling?
Tambahkan pointer prevSibling atau indeks child-set, tetapi Anda harus memelihara lebih banyak pointer pada setiap link dan cut. Bandingkan biaya ruang dan pemeliharaan tersebut dengan pemindaian.
Pertanyaan lanjutan 3: Bagaimana cara menghapus handle sembarang?
Turunkan key-nya menjadi tak hingga negatif, panggil decrease-key, lalu delete-min. Pastikan komparator dan sentinel aman, serta batalkan validitas handle dengan benar.
Pertanyaan lanjutan 4: Kapan Anda akan memilih Fibonacci heap?
Pertimbangkan ketika batas teramortisasi decrease-key teoretis dan bukti algoritmik lebih penting daripada kompleksitas implementasi. Kode rekayasa perangkat lunak tetap membutuhkan pengukuran lokalitas, memori, dan beban kerja nyata.