Apakah ada tumpukan stabil?

Apakah ada struktur data antrian prioritas yang mendukung operasi berikut?

• Sisipkan (x, p) : Tambahkan catatan baru x dengan prioritas p
• StableExtractMin () : Kembalikan dan hapus catatan dengan prioritas minimum, putuskan hubungan dengan urutan penyisipan .

Jadi, setelah Sisipan (a, 1), Sisipkan (b, 2), Sisipkan (c, 1), Sisipkan (d, 2), urutan StableExtractMin's akan mengembalikan a, lalu c, lalu b, lalu d.

Jelas salah satu bisa menggunakan apa saja struktur data antrian prioritas dengan menyimpan pasangan sebagai prioritas yang sebenarnya, tapi aku tertarik dalam struktur data yang tidak secara eksplisit menyimpan kali penyisipan (atau perintah penyisipan), dengan analogi untuk penyortiran stabil.$(p, time)$

Setara (?): Apakah ada heaport versi stabil yang tidak membutuhkan ruang ekstra?$\Omega(n)$

Metode Bently-Saxe memberikan antrian prioritas stabil yang cukup alami.

Simpan data Anda dalam urutan array yang diurutkan . A i memiliki ukuran 2 i . Setiap array juga memiliki counter c i . Entri array A i [ c i ] , … , A i [ 2 i - 1 ] berisi data.$A_0,\ldots,A_k$$A_i$$2^i$$c_i$$A_i[c_i],\ldots,A_i[2^i-1]$

Untuk setiap , semua elemen di A i ditambahkan baru-baru ini daripada di A i + 1 dan dalam setiap A i elemen yang diperintahkan oleh nilai dengan ikatan yang rusak dengan menempatkan unsur-unsur yang lebih tua menjelang elemen baru. Perhatikan bahwa ini berarti kita dapat menggabungkan A i dan A i + 1 dan mempertahankan pemesanan ini. (Dalam kasus ikatan selama penggabungan, ambil elemen dari A i + 1. )$i$$A_i$$A_{i+1}$$A_i$$A_i$$A_{i+1}$$A_{i+1}$

Untuk menyisipkan nilai , temukan i terkecil sehingga A i berisi 0 elemen, gabungkan A 0 , … , A i - 1 dan x , simpan ini dalam A i dan set c 0 , … , c i dengan tepat.$x$$i$$A_i$$A_0,\ldots,A_{i-1}$$x$$A_i$$c_0,\ldots,c_i$

Untuk mengekstrak min, cari indeks terbesar sehingga elemen pertama dalam A i [ c i ] adalah minimum di atas semua i dan selisih c i .$i$$A_i[c_i]$$i$$c_i$

Dengan argumen standar, ini memberikan waktu diamortisasi per operasi dan stabil karena urutan yang dijelaskan di atas.$O(\log n)$

Untuk urutan penyisipan dan ekstraksi, ini menggunakan entri n array (jangan biarkan array kosong) ditambah O ( log n ) kata-kata data pembukuan. Itu tidak menjawab versi Mihai dari pertanyaan, tetapi itu menunjukkan bahwa kendala stabil tidak memerlukan banyak ruang overhead. Secara khusus, ini menunjukkan bahwa tidak ada Ω ( n ) batas bawah pada ruang ekstra yang dibutuhkan.$n$$n$$O(\log n)$$\Omega(n)$

$n$$n$

$A_k,\ldots,A_0$$A_k$$A_{k-1}$$n$$n$$i$$A_i$$2^i$

$n$$A_0,\ldots,A_i$

$c_i$$A_i$$c_i$$2^i-c_i-1$$O(\log n)$$A_0[0],\ldots,A_k[0]$$A_i[0]$$A_i[0]$$A_i$$A_i[c_i]$$A_i[0]$$A_i[c_i]$

$n$

Saya tidak yakin apa kendala Anda; apakah kualifikasi berikut memenuhi syarat? Simpan data dalam sebuah array, yang kami tafsirkan sebagai pohon biner implisit (seperti tumpukan biner), tetapi dengan item data di tingkat bawah pohon daripada di node internal. Setiap simpul internal pohon menyimpan nilai yang lebih kecil dari dua anaknya yang disalin; dalam hal ikatan, salin anak kiri.

Untuk menemukan minimum, lihat pada akar pohon.

Untuk menghapus elemen, tandai sebagai dihapus (lazy deletion) dan menyebar pohon (setiap node di jalan ke root yang menyimpan salinan elemen yang dihapus harus diganti dengan salinan anak yang lain). Pertahankan hitungan elemen yang dihapus dan jika terlalu banyak fraksi dari semua elemen maka bangun kembali struktur yang mempertahankan urutan elemen di tingkat bawah - pembangunan kembali membutuhkan waktu linier sehingga bagian ini hanya menambahkan waktu diamortisasi konstan ke kompleksitas operasi.

Untuk memasukkan elemen, tambahkan ke posisi bebas berikutnya di baris bawah pohon dan perbarui jalur ke root. Atau, jika baris bawah menjadi penuh, gandakan ukuran pohon (sekali lagi dengan argumen amortisasi; perhatikan bahwa bagian ini tidak berbeda dengan kebutuhan untuk membangun kembali ketika biner standar menumpuk melebihi susunannya).

Ini bukan jawaban untuk versi pertanyaan Mihai yang lebih ketat, karena ia menggunakan memori dua kali lebih banyak daripada struktur data implisit yang sebenarnya, bahkan jika kita mengabaikan biaya ruang untuk menangani penghapusan dengan malas.

Apakah berikut ini interpretasi yang valid untuk masalah Anda:

Anda harus menyimpan kunci N dalam larik A [1..N] tanpa informasi tambahan sehingga Anda dapat mendukung: * masukkan kunci * hapus min, yang mengambil elemen yang dimasukkan paling awal jika ada beberapa minima

Ini tampak cukup sulit, mengingat bahwa sebagian besar struktur data implisit memainkan trik penyandian bit dalam pemesanan lokal beberapa elemen. Di sini jika banyak orang sama, pemesanan mereka harus dilestarikan, jadi tidak ada trik seperti itu yang mungkin.

Menarik.

Jawaban singkat: Anda tidak bisa.

Jawaban yang sedikit lebih panjang:

$\Omega(n)$$\Omega(n)$

$addr(X) < addr(Y)$

Jawaban yang sangat panjang dengan pseudo-matematika tidak pasti yang tidak pasti:

Catatan: bagian paling akhir tidak jelas, seperti yang disebutkan. Jika beberapa orang matematika dapat memberikan versi yang lebih baik, saya akan berterima kasih.

$P$

$(a,1) < (a,2)$$(a,1) = (a,1)$$(a,1)$$(b,1)$

$X < Y$$X$$Y$

$(?,1)$$?$

• $X - log_2(P)$$2^X$
• $P$

$X - log_2(P)$$O(n)$$n$

Sekarang, berapa banyak bit informasi yang diberikan "sel" memori masing-masing kepada kita?

• $W$$W$
• $X$

$P \geq 1$$X - log_2(P) < X$

Jadi, untuk menyimpan semua informasi kami, kami memiliki dua kemungkinan:

• Simpan urutan penyisipan di alamat, dan muatan di memori.
• Simpan keduanya dalam memori dan biarkan alamatnya gratis untuk penggunaan lainnya.

Jelas, untuk menghindari pemborosan, kami akan menggunakan solusi pertama.

Sekarang untuk operasi. Saya kira Anda ingin memiliki:

• $Insert(task, priority)$$O(log n)$
• $StableExtractMin()$$O(log n)$

$StableExtractMin()$

Algoritma yang benar-benar sangat umum berjalan seperti ini:

1. $O(log n)$
2. $O(log n)$
3. Kembalikan.

$0(1)$$O(1)$$O(1)$

$O(log n)$$2^(X - log_2(P))$

$X - log_2(P)$$O(log n)$$O(log n)$

$O(log n)$

$O(log n)$$X - log_2(P)$

$O(log n)$

$X - log_2(P)$$O(log n)$

Algoritme penyisipan biasanya hanya perlu memperbarui bagian dari informasi ini, saya tidak berpikir itu akan lebih mahal (memori-bijaksana) untuk melakukannya dengan cepat.

$X - log_2(P)$

• $X - log_2(P)$
• $P$
• $X - log_2(P)$

$\Omega(n)$

Jika Anda menerapkan antrian prioritas Anda sebagai pohon biner seimbang (pilihan populer), maka Anda hanya perlu memastikan bahwa ketika Anda menambahkan elemen ke pohon, itu akan disisipkan di sebelah kiri setiap elemen dengan prioritas yang sama.
Dengan cara ini, urutan penyisipan dikodekan dalam struktur pohon itu sendiri.

Saya pikir itu tidak mungkin

kasus nyata:

       x
    x    x
  x  x  1  x
1  x  

min heap dengan semua x> 1

heapifying pada akhirnya akan memberikan sesuatu pilihan seperti itu

       x
    1    1
  x  x  x  x
x  x  

sekarang yang 1 untuk disebarkan ke root?