Apakah ada tumpukan stabil?

32

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?Ω(n)

Jeffε
sumber
Saya pikir maksud Anda "a, lalu c, lalu b, lalu d"?
Ross Snider
Tumpukan dengan daftar catatan tertaut + pohon biner seimbang yang dikunci pada prioritas menunjuk ke daftar tertaut yang sesuai tidak akan berfungsi? Apa yang saya lewatkan?
Aryabhata
Orang bodoh: Itu menyimpan urutan penyisipan secara eksplisit, itulah yang ingin saya hindari. Saya mengklarifikasi pernyataan masalah (dan memperbaiki kesalahan ketik Ross).
Jeffε

Jawaban:

16

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.A0,,AkAi2iciAi[ci],,Ai[2i1]

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. )iAiAi+1AiAiAi+1Ai+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.xiAiA0,,Ai1xAic0,,ci

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

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

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.nnO(logn)Ω(n)

nn

Ak,,A0AkAk1nniAi2i

nA0,,Ai

ciAici2ici1O(logn)A0[0],,Ak[0]Ai[0]Ai[0]AiAi[ci]Ai[0]Ai[ci]

n

Pat Morin
sumber
1
Ini menggunakan potensial O (n) ruang ekstra pada saat tertentu setelah ekstraksi O (n), bukan? Pada titik ini Anda sebaiknya menyimpan prioritas juga ...
Mehrdad
10

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.

David Eppstein
sumber
Saya suka ini. Sama seperti dengan min-heap pohon implisit reguler, mungkin pohon implisit 3-ary atau 4-ary akan lebih cepat karena efek cache (walaupun Anda membutuhkan lebih banyak perbandingan).
Jonathan Graehl
8

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.

Mihai
sumber
1
Saya pikir ini harus menjadi komentar, bukan jawaban, karena tidak benar-benar menjawab pertanyaan awal. (Anda dapat menghapusnya dan menambahkannya sebagai komentar.)
Jukka Suomela
5
Ya, situs web ini agak konyol. Kami memiliki reputasi, bonus, penghargaan, segala macam cara untuk berkomentar yang tidak dapat saya bayangkan. Saya berharap ini akan terlihat kurang seperti permainan anak-anak.
Mihai
1
Saya pikir dia perlu lebih banyak perwakilan untuk mengirim komentar. itulah masalahnya.
Suresh Venkat
@ Suresh: Oh, benar, saya tidak ingat itu. Bagaimana kita seharusnya menangani situasi semacam ini (yaitu, pengguna baru perlu meminta klarifikasi sebelum menjawab pertanyaan)?
Jukka Suomela
2
tidak ada jalan keluar yang mudah. Saya sering melihat ini di MO. Mihai tidak akan kesulitan mendapatkan perwakilan, jika itu Mihai, saya pikir itu :)
Suresh Venkat
4

Jawaban singkat: Anda tidak bisa.

Jawaban yang sedikit lebih panjang:

Ω(n)Ω(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<YXY

(?,1)?

  • Xlog2(P)2X
  • P

Xlog2(P)O(n)n

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

  • WW
  • X

P1Xlog2(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(logn)
  • StableExtractMin()O(logn)

StableExtractMin()

Algoritma yang benar-benar sangat umum berjalan seperti ini:

  1. O(logn)
  2. O(logn)
  3. Kembalikan.

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

O(logn)2(Xlog2(P))

Xlog2(P)O(logn)O(logn)

O(logn)

O(logn)Xlog2(P)

O(logn)

Xlog2(P)O(logn)

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


Xlog2(P)

  • Xlog2(P)
  • P
  • Xlog2(P)

Ω(n)

Suzanne Dupéron
sumber
apakah Anda benar-benar berniat untuk membuat jawaban Anda CW?
Suresh Venkat
Iya nih. Jawaban saya tidak 100% benar, seperti yang dinyatakan di dalam, dan itu akan baik jika ada yang bisa memperbaikinya bahkan jika saya tidak di SO lagi atau apa pun. Pengetahuan harus dibagikan, pengetahuan harus diubah. Tapi mungkin saya salah mengerti penggunaan CW, kalau begitu, tolong beri tahu saya :). EDIT: whoops, memang saya baru tahu bahwa saya tidak akan mendapatkan perwakilan dari posting CW dan bahwa kontennya adalah CC-wiki yang dilisensikan dengan cara apa pun ... Sayang sekali :).
Suzanne Dupéron
3

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.

TonyK
sumber
1
Tetapi ini menambah O (n) ruang untuk pointer, yang saya pikir adalah apa yang ingin dihindari penanya?
Jeremy
-1

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?

ratchet freak
sumber