Temu duga pengekodan: Bagaimanakah anda akan melaksanakan pairing heap dengan decrease-key?

Gesaan dan konteks

Laksanakan baris gilir keutamaan minimum boleh gabung (meldable min-priority queue) untuk penjadual acara yang keutamaan tugasnya boleh menurun. Binary heap mengendalikan operasi asas, tetapi meld dan decrease-key menambah kos. Laksanakan pairing heap dengan pemegang (handles), pemautan (linking), penggabungan dua laluan, pemadaman, dan kes-kes pinggir.

Pairing heap diperkenalkan pada tahun 1986 sebagai self-adjusting heaps yang bertujuan untuk menggabungkan pelaksanaan mudah dengan prestasi praktikal yang baik; kertas asal hanya memberikan analisis kerumitan separa. Temu duga ini menguji sama ada anda membezakan ketepatan kod, penaakulan terlunas, dan dakwaan kerumitan yang belum terbukti.

Perkara yang dinilai oleh penemu duga

Merangkumi varian min-heap, meld masa malar, penggandingan adik-beradik dua laluan, pemegang lapuk (stale handles), decrease-key potong-dan-paut semula, kekunci kosong dan pendua, pemilikan memori, serta pertukaran berbanding binary heap dan Fibonacci heap.

Soalan penjelasan untuk ditanya

• Adakah decrease-key diperlukan, atau hanya push/pop, dan apakah campuran operasinya?
• Adakah pemegang nod mesti kekal stabil, dan bagaimanakah pemegang lapuk dikesan?
• Adakah rekursi dibenarkan, dan apakah saiz timbunan maksimum serta belanjawan tindanan (stack budgets)?
• Bolehkah pembanding melontarkan ralat atau berubah, dan adakah keutamaan pendua disokong?
• Adakah matlamatnya kejelasan pengajaran, kelajuan praktikal pemalar rendah, atau bukti kes terburuk yang ketat?

Jawapan 30 saat

“Setiap nod menyimpan kekunci, muatan (payload), ibu bapa, anak pertama, dan adik-beradik seterusnya, dengan pemegang menunjuk ke nod tersebut. Link membandingkan dua punca dan menjadikan punca yang lebih besar sebagai anak pertama kepada punca yang lebih kecil. Delete-min menanggalkan punca, memautkan adik-beradik dari kiri ke kanan secara berpasangan, kemudian menggabungkannya dari kanan ke kiri. Decrease-key memotong nod bukan punca dan menggabungkannya (meld) sebagai punca. Jejaki keadaan pemegang dan huraikan kerumitan menggunakan analisis terlunas dan analisis yang telah mantap.”

Panduan mendalam langkah demi langkah

Langkah 1: Tentukan nod dan pemegang

Simpan kekunci, payload, ibu bapa, anak pertama, dan adik-beradik kanan dalam setiap nod. Pemegang menunjuk ke nod dan membawa penanda hidup atau generasi, menghalang decrease-key selepas pemadaman. Punca tidak mempunyai ibu bapa dan penghujung senarai adik-beradik adalah nol (null).

Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }

Pembanding hanya menyusun nilai dan tidak mengubah nod. Anggap kekunci yang sama sebagai nod yang berbeza dan gunakan dasar kestabilan yang diperlukan.

Langkah 2: Laksanakan link dan meld

link(a, b) membandingkan dua punca, menjadikan punca dengan kekunci lebih besar sebagai anak pertama kepada punca dengan kekunci lebih kecil, dan mengemas kini penuding ibu bapa serta adik-beradik. meld hanya memautkan dua punca; timbunan kosong mengembalikan punca yang satu lagi.

Selepas setiap kemas kini penuding, sahkan (assert) bahawa punca tidak mempunyai ibu bapa, setiap anak menunjuk kembali ke ibu bapanya, dan saiz tidak berubah. Binaan nyahpepijat boleh merentasi struktur untuk kitaran, tetapi operasi pengeluaran tidak sepatutnya melakukan semakan linear setiap kali.

Langkah 3: Laksanakan insert dan find-min

insert mencipta timbunan elemen tunggal, menggabungkannya (meld) dengan punca, dan mengembalikan pemegang yang stabil. find-min membaca punca; timbunan kosong mengembalikan hasil kosong atau ralat API dan bukannya menyahrujuk nol.

Jika pemanggil mengekalkan pemegang, mengalihkan atau membesarkan timbunan mestilah tidak membatalkannya. Peruntukkan nod secara bebas atau gunakan lapisan bukan langsung yang stabil, dan dokumentasikan sama ada timbunan memiliki nod atau hanya muatan.

Langkah 4: Laksanakan delete-min dua laluan

Selepas membuang punca, tanggalkan senarai anaknya menjadi senarai punca. Dalam laluan pertama, pautkan punca bersebelahan dari kiri ke kanan secara berpasangan; kekalkan punca terakhir apabila bilangannya ganjil. Dalam laluan 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 -= 1

Kosongkan penuding ibu bapa dan adik-beradik lama semasa penggabungan supaya punca yang dikeluarkan tidak dikekalkan. Gunakan senarai lelaran untuk rantai adik-beradik yang panjang bagi mengelakkan limpahan tindanan (stack overflow).

Langkah 5: Laksanakan decrease-key

Tolak kekunci baharu yang tidak lebih kecil, atau tentukan operasi increase-key yang berasingan. Untuk punca, kemas kini kekunci sahaja. Untuk bukan punca, potong daripada senarai anak ibu bapanya, baiki penuding adik-beradik, dan gabungkannya (meld) sebagai punca bebas.

Pemotongan memerlukan adik-beradik sebelumnya: imbas senarai ibu bapa, atau tambah penuding prevSibling dan terima penyelenggaraan tambahan. Kembalikan ralat untuk pemegang lapuk, nod daripada timbunan lain, atau timbunan yang telah dimusnahkan.

Langkah 6: Uji varian dan kerumitan

Gunakan ujian pembezaan rawak terhadap baris gilir keutamaan standard, meliputi kekunci pendua, timbunan kosong, decrease-key berulang, memadam setiap nod, dan meld rawak. Selepas setiap operasi, sahkan bahawa punca adalah minimum, saiz sepadan dengan nod hidup, dan pautan ibu bapa-anak adalah tidak berkitar (acyclic).

Asingkan batas yang terbukti, intuisi terlunas, dan ukuran. insert dan meld pairing-heap mempunyai pemalar yang kecil, tetapi analisis ketat untuk delete-min dan decrease-key bukanlah lesen untuk mendakwa bahawa setiap operasi adalah O(log n) dalam kes terburuk. Nyatakan andaian dan bandingkan binary heap dan Fibonacci heap.

Contoh jawapan yang mantap

Saya akan menggunakan penuding ibu bapa, anak pertama, adik-beradik seterusnya dan pemegang yang stabil untuk link, meld, delete-min dua laluan, dan decrease-key. decrease-key bukan punca dipotong daripada senarai adik-beradiknya sebelum digabungkan sebagai punca baharu; delete-min menggandingkan dari kiri ke kanan dan menggabungkan dari kanan ke kiri. Saya akan melakukan ujian pembezaan terhadap baris gilir keutamaan standard, menyemak varian bukan berkitar dan saiz, serta membezakan analisis terlunas, batas kes terburuk, dan penanda aras praktikal.

Kesilapan biasa

• Hanya menukar kekunci → susunan timbunan dan pautan ibu bapa rosak → potong dan meld setiap decrease-key bukan punca.
• Menterbalikkan dua laluan → bentuk dan hasil menjadi salah → gandingkan dari kiri ke kanan, kemudian gabungkan dari kanan ke kiri.
• Menggunakan pemegang yang dipadamkan → use-after-free atau mutasi rentas timbunan → batalkan dan sahkan pemilikan.
• Mendakwa setiap operasi adalah kes terburuk O(log n) → kerumitan tiada sokongan bukti → asingkan analisis terlunas, analisis separa, dan ukuran.
• Melakukan rekursi melalui senarai adik-beradik yang panjang → limpahan tindanan (stack overflow) → gunakan senarai lelaran.

Soalan susulan dan jawapan

Susulan 1: Mengapa tidak menggunakan binary heap secara langsung?

Binary heap mempunyai susun atur tatasusunan yang mudah dan batas yang stabil; pairing heap mungkin mempunyai pemalar yang lebih kecil dengan meld dan decrease-key yang kerap. Pilih menggunakan campuran operasi, lokaliti memori, dan keperluan bukti.

Susulan 2: Bagaimanakah decrease-key boleh mengelak daripada mengimbas adik-beradik?

Tambah penuding prevSibling atau indeks set anak, tetapi kekalkan lebih banyak penuding pada setiap link dan cut. Bandingkan kos ruang dan penyelenggaraan tersebut dengan pengimbasan.

Susulan 3: Bagaimanakah anda memadamkan pemegang sewenang-wenangnya?

Kurangkan kekuncinya kepada infiniti negatif, panggil decrease-key, dan kemudian delete-min. Pastikan pembanding dan sentinel adalah selamat, dan batalkan pemegang dengan betul.

Susulan 4: Bilakah anda akan memilih Fibonacci heap?

Pertimbangkannya apabila batas terlunas decrease-key secara teori dan bukti algoritma lebih penting daripada kerumitan pelaksanaan. Kod kejuruteraan masih memerlukan pengukuran lokaliti, memori, dan beban kerja sebenar.