Temu duga pengekodan: Laksanakan timbunan radiks (radix heap) integer monoton

Gesaan dan kes penggunaan

Radix heap ialah struktur integer untuk baris gilir keutamaan monoton, berguna dalam algoritma seperti Dijkstra di mana kunci yang diekstrak adalah tidak berkurang. Ia menggunakan kunci terakhir yang diekstrak sebagai sempadan dan mengumpulkan ke dalam baldi mengikut bit berbeza tertinggi.

Perkara yang dinilai oleh penemu duga

• Sama ada kunci yang dimasukkan dikekang oleh kunci terakhir yang diekstrak.
• Sama ada bit berbeza tertinggi dan julat baldi adalah betul.
• Sama ada baldi bukan kosong terkecil diagihkan semula dengan asas baharu.
• Sama ada varian baldi dan kunci minimum dikekalkan.
• Sama ada baris gilir kosong, limpahan (overflow), dan kunci ke belakang dikendalikan.
• Sama ada pengagihan semula dan kerumitan terlunas diterangkan secara jujur.

Penjelasan sebelum menjawab

• Adakah kunci merupakan integer tanpa tanda dengan lebar tetap atau kejituan sewenang-wenangnya?
• Bolehkah kunci yang dimasukkan lebih kecil daripada kunci terakhir yang diekstrak?
• Patutkah muatan kunci yang sama bersifat stabil?
• Adakah hanya pop-min diperlukan, atau juga decrease-key dan pemadaman?
• Apakah yang patut dikembalikan oleh pop kosong dan limpahan?
• Adakah kejelasan, faktor pemalar rendah, atau batas asimptotik menjadi keutamaan?

Rangka kerja jawapan 30 saat

"Saya mengekalkan last, kunci yang paling baru diekstrak, dan baldi W+1. Kunci yang sama dengan last pergi ke baldi 0; jika tidak, baldinya ialah bit_length(key XOR last). Jika baldi 0 kosong, saya mencari baldi bukan kosong terkecil, mengimbas kunci minimumnya sebagai last baharu, mengagihkan semula baldi tersebut, dan melakukan pop dari baldi 0. Kunci di bawah last akan ditolak."

Panduan mendalam langkah demi langkah

Langkah 1: Nyatakan varian (invariants). last tidak pernah berkurang, setiap kunci yang belum selesai memenuhi key >= last, dan baldi i mengandungi kunci yang bit berbeza tertingginya daripada last ialah i.

Langkah 2: Kira baldi. Indeks ialah 0 apabila key == last; jika tidak, gunakan bit_length(key XOR last). Kunci W-bit memerlukan baldi W+1.

Langkah 3: Laksanakan push. Semak bukan negatif, lebar bit, dan key >= last, kemudian letakkan (key, value) dalam baldinya; kunci yang sama boleh wujud bersama.

Langkah 4: Laksanakan pop. Kembalikan dari baldi 0 apabila tidak kosong. Jika tidak, cari baldi bukan kosong terendah, imbas kunci minimumnya, dan berikannya kepada last.

Langkah 5: Agihkan semula. Kosongkan baldi tersebut dan kira semula indeks setiap item terhadap last baharu; indeks berkurang dan sekurang-kurangnya satu item mencapai baldi 0.

Langkah 6: Kendalikan sempadan. Kembalikan hasil kosong yang ditakrifkan; tolak kunci di luar lebar bit atau di bawah last untuk mengelakkan kelakuan XOR dan indeks yang tidak ditakrifkan.

Langkah 7: Nyatakan kerumitan. Setiap item diagihkan semula beberapa kali yang dibatasi oleh saiz perkataan W; kos terlunas biasa ialah O(W), ruang ialah O(n + W), dan ia tidak secara universal lebih pantas daripada binary heap.

Model jawapan berkualiti tinggi

"Saya menggunakan kunci tanpa tanda 64-bit dan 65 baldi. last bermula pada sifar; kunci di bawah last ditolak, jika tidak bit_length(key XOR last) memilih baldinya. pop mengambil dari baldi 0, atau mencari baldi bukan kosong terendah, mengimbas kunci minimumnya ke dalam last, dan mengagihkan semula. Kunci yang sama mengekalkan muatan berasingan. Pop kosong mengembalikan nilai kosong, dan limpahan atau kunci ke belakang akan gagal. Setiap item hanya diagihkan semula sebanyak bilangan yang dibatasi saiz perkataan, dengan ruang untuk item ditambah baldi."

Kesilapan biasa

• Membenarkan kunci ke belakang → varian baldi gagal → tolak key < last.
• Menggunakan log2(key) untuk baldi → asas semasa diabaikan → gunakan key XOR last.
• Mengekalkan last tidak berubah selepas pengagihan semula → pengekstrakan boleh menjadi salah → imbas nilai minimum terlebih dahulu.
• Mengambil item pertama dalam baldi → ia mungkin bukan nilai minimum → imbas untuk mendapatkan kunci minimum.
• Mendakwa setiap operasi adalah O(1) → saiz perkataan dan pengagihan semula diabaikan → nyatakan andaian W dan pelunasan (amortization).

Soalan susulan dan jawapan

Soalan susulan 1: Mengapa ia sesuai untuk Dijkstra?

Jarak yang diekstrak adalah tidak berkurang, dan jarak calon baharu tidak berada di bawah nilai minimum semasa, memenuhi keperluan kunci monoton.

Soalan susulan 2: Bagaimana jika decrease-key sewenang-wenangnya diperlukan?

Radix heap tidak sesuai untuk kunci ke belakang. Gunakan binary heap atau pairing heap, atau simpan versi dan buang entri lapuk secara lazy.

Soalan susulan 3: Mengapa baldi 0 boleh di-pop secara terus?

Setiap kunci dalam baldi 0 adalah sama dengan last, jadi semuanya adalah kunci minimum semasa.

Soalan susulan 4: Mengapa indeks yang diagihkan semula berkurang?

last baharu ialah nilai minimum baldi; bit berbeza tertinggi bagi setiap item lain adalah tidak lebih besar daripada indeks baldi lama, dan sekurang-kurangnya satu mencapai baldi 0.

Soalan susulan 5: Bagaimanakah anda mengekalkan kestabilan kunci yang sama?

Tambahkan nombor jujukan monoton pada muatan dan pilih (key, sequence) dalam baldi 0; jika tidak, kestabilan adalah pilihan.

Soalan susulan 6: Bagaimana dengan kunci negatif?

Petakannya ke dalam ruang tertib tanpa tanda atau tentukan kunci bukan negatif sahaja. XOR bertanda tanpa definisi susunan adalah tidak selamat.

Soalan susulan 7: Bilakah binary heap lebih baik?

Gunakan binary heap apabila kunci bukan integer monoton, saiz perkataan adalah besar, kemas kini adalah rumit, atau kesederhanaan dan keumuman lebih penting daripada batas khusus.