Apakah ada antrian prioritas dengan ekstrak ?

Ada banyak sekali struktur data yang mengimplementasikan antarmuka antrian prioritas:

• Sisipkan: masukkan elemen ke dalam struktur
• Get-Min: kembalikan elemen terkecil dalam struktur
• Extract-Min: menghapus elemen terkecil dalam struktur

Struktur data umum yang mengimplementasikan antarmuka ini adalah (min) tumpukan .

Biasanya, waktu berjalan (diamortisasi) dari operasi ini adalah:

• Sisipkan: (kadang-kadang )O ( log n $\mathcal{O}(1)$$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(\log n)$

The Fibonacci tumpukan mencapai masa berjalan misalnya. Sekarang, pertanyaan saya adalah sebagai berikut:

Apakah ada struktur data dengan waktu berjalan (diamortisasi) berikut ini?

• Sisipkan:$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(1)$

Jika kita dapat membangun struktur seperti itu dalam waktu diberikan input yang diurutkan, maka kita dapat misalnya menemukan persimpangan garis pada input yang sudah diurutkan sebelumnya dengan persimpangan benar-benar lebih cepat daripada jika kita menggunakan antrian prioritas 'biasa'.o ( $\mathcal{O}(n)$$o\left(\frac{n}{\log n}\right)$

Gagasan kami adalah menggunakan pohon ulir berulir . Selain artikel Wikipedia, kami akan mengaitkan pohon sehingga setiap node memiliki pointer ke penggantinya dalam urutan traversal; kami juga memegang pointer ke elemen terkecil di pohon.nextstart

Sangat mudah untuk melihat bahwa mengekstraksi elemen terkecil dimungkinkan dalam waktu (terburuk) : cukup ikuti pointer, hapus minimum dan ubah pointer ke minimum . Minimal tidak pernah bisa memiliki anak kiri; jika memiliki anak yang tepat, kita letakkan di tempat minimum di pohon. Kami tidak melakukan operasi splay pohon splay biasanya akan lakukan. Hasilnya adalah pohon pencarian yang masih cukup seimbang: karena kami hanya menghapus node di sisi kiri, kami tahu bahwa ketika jumlah node (dalam subtree yang terpengaruh) turun menjadi sekitar setengah dari jumlah asli karena penghapusan, maka (sub ) tinggi pohon berkurang satu.$\mathcal{O}(1)$startnext

Penyisipan dimungkinkan dalam waktu ; operasi zig-zag (dan apa yang tidak) di sini juga akan menyeimbangkan kembali pohon dengan baik.$\mathcal{O}(\log n)$

Ini adalah sketsa kasar yang terbaik. Kredit diberikan kepada F. Weinberg yang bingung dengan pertanyaan saya dan penasihat kami M. Nebel yang menyebutkan pohon melebar, tentang satu-satunya varian pohon yang belum kami coba.

• Sisipkan:$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(1)$

Waktu yang diamortisasi

Implementasi sederhana dari antrian prioritas (misalnya BST seimbang, atau tumpukan biner standar) dapat mencapai waktu berjalan (diamortisasi) ini dengan hanya membebankan biaya Ekstrak-Min untuk menyisipkan, dan mempertahankan penunjuk ke elemen minimum. Misalnya, Anda dapat memiliki fungsi potensial yaitu . Kemudian memasukkan elemen baru meningkatkan potensi sebesar , dan sehingga biaya amortisasi insert masih , tetapi Extract-Min () mengurangi potensi oleh , dan jadi biaya yang diamortisasi hanya .O ( log n ) O ( log n ) Ω ( log n ) O ( 1 $cn \log n$$O(\log n)$$O(\log n)$$\Omega(\log n)$$O(1)$

Kasus terburuk

Anda dapat menggunakan struktur data yang ada dalam literatur: pohon pencarian jari, dan cukup mempertahankan pointer ke elemen minimum. Lihat survei ini untuk ikhtisar, dan makalah 1988 oleh Levcopoulos dan Overmars untuk versi yang dapat diterapkan yang memenuhi kebutuhan Anda.

2-4 pohon telah diamortisasi modifikasi di lokasi yang diketahui. Artinya, jika Anda memiliki pointer ke beberapa lokasi di pohon, Anda dapat menghapus atau menambahkan elemen di sana dalam waktu diamortisasi.O ( 1 $O(1)$$O(1)$

Anda bisa menyimpan pointer ke elemen minimum dan simpul root di pohon 2-4. Sisipan harus melalui simpul akar. Memperbarui pointer ke minimum adalah sepele setelah deleteMin, dan deleteMins adalah (diamortisasi) waktu.$O(1)$

Catatan menarik: pohon merah-hitam hanyalah cara memandang 2-4 pohon. Perancang pelaksana perpustakaan standar C ++ 98 diharapkan untuk memasok wadah berbasis pohon merah-hitam, dan standar tersebut menetapkan bahwa memasukkan dan menghapus harus waktu diamortisasi di lokasi yang diketahui (yang mereka sebut "iterators" ). Namun, ini sebenarnya jauh lebih sulit untuk pohon merah-hitam daripada untuk 2-4 pohon, karena membutuhkan simpul penandaan malas yang perlu di-recolored. Sepengetahuan saya, tidak ada implementasi dari perpustakaan standar C ++ 98 yang memenuhi persyaratan tertentu.$O(1)$

Berdasarkan permintaan, berikut adalah struktur yang saya temukan setelah saya merumuskan pertanyaan:

Ide dasarnya adalah menggunakan pohon kambing hitam berulir bersama dengan pointer ke minimum (dan untuk ukuran yang baik, maksimum juga). Alternatif yang lebih sederhana untuk threading adalah mempertahankan pointer pendahulu dan penerus di setiap node (yang setara, lebih sederhana, tetapi memiliki lebih banyak overhead). Saya datang untuk menyebutnya tumpukan kambing hitam , hanya untuk memberinya beberapa nama.

Hanya struktur dasar ini memberi Anda operasi ini:

• Cari: diberi kunci, mengembalikan pointer ke simpul yang sesuai pada waktu .$\mathcal{O}(\log n)$
• Sisipkan: diberikan kunci, memasukkan kunci ke dalam struktur, mengembalikan pointer ke simpul itu dalam waktu .$\mathcal{O}(\log n)$
• Predecessor / successor: diberi pointer, mengembalikan penerus atau pendahulunya dalam waktu .$\mathcal{O}(1)$
• Get-Min / Max: mengembalikan pointer ke minimum atau maksimum.

Dalam analisis pohon kambing hitam, keseimbangan biaya penghapusan dianalisis sebagai , tetapi analisis sebenarnya memberikan keseimbangan overhead dari (yang diabaikan dalam makalah karena mereka juga menghitung waktu untuk menemukan simpul yang akan dihapus). Jadi, jika kita memiliki pointer ke sebuah node, kita dapat menghapusnya dalam waktu konstan (Anda dapat melakukan ini di pohon pencarian biner dalam waktu ) dan dikombinasikan dengan overhead of balancing, ini memberi waktu hapus:O ( 1 ) O ( log n ) O ( 1 ) O ( 1 ) O ( 1 $\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(1)$$\mathcal{O}(1)$

• Hapus: diberi pointer, menghapus simpul dalam waktu .$\mathcal{O}(1)$

Menggabungkan ini:

• Extract-Min / Max: menghapus simpul minimum / maksimum dalam waktu .$\mathcal{O}(1)$

Anda dapat melakukan sedikit lebih banyak dengan pointer: misalnya tidak sulit untuk mempertahankan pointer ke median atau statistik urutan lainnya, sehingga Anda dapat mempertahankan jumlah pointer yang konstan jika Anda membutuhkannya.

Beberapa hal lain:

• Membangun: diberikan kunci dalam urutan diurutkan, membangun tumpukan kambing hitam dalam waktu .$n$$\mathcal{O}(n)$
• Saldo: menyeimbangkan pohon sehingga membentuk pohon pencarian biner seimbang sempurna (mengurangi overhead pencarian) dalam waktu (Anda dapat melakukan ini dengan faktor konstan lebih cepat dari yang disarankan oleh makalah, dengan memanfaatkan dari pendahulu / penggantinya).$\mathcal{O}(n)$

Dan akhirnya, saya cukup yakin Anda dapat mendukung operasi ini, tetapi saya perlu memikirkan ini lebih banyak sebelum mengetahui ini dengan pasti:

• Sisipkan-New-Min / Max: diberi kunci yang lebih kecil / lebih besar dari kunci apa pun yang ada dalam struktur, memasukkan kunci ke dalam struktur, mengembalikan pointer ke simpul itu dalam waktu .$\mathcal{O}(1)$

Tumpukan lunak adalah modifikasi halus dari antrian binomial. Struktur data diperkirakan dengan parameter kesalahan . Ini mendukung masukkan, hapus, berbaur dan temukan. The diamortisasi kompleksitas setiap operasi adalah , kecuali untuk insert yang mengambil waktu. Kebaruan dari heap lunak adalah dalam mengalahkan batas logaritmik pada kompleksitas tumpukan dalam model berbasis perbandingan. Untuk memecahkan penghalang teoretis informasi, entropi dari struktur data dikurangi dengan secara artifisial meningkatkan nilai beberapa kunci. Ini disebut merusak kunci. Struktur data sepenuhnya berbasis pointer (tidak ada array atau asumsi numerik) dan optimal untuk setiap nilai$\epsilon$$O(1)$$\log (1/\epsilon)$$\epsilon$ dalam model berbasis perbandingan.

Aplikasi soft heap termasuk menghitung pohon spanning minimum untuk grafik, menjaga persentil secara dinamis dan statistik urutan waktu linier. Itu dapat juga digunakan untuk perhitungan perkiraan, seperti perkiraan penyortiran di mana peringkat elemen tidak pernah berbeda lebih dari dari peringkat sebenarnya.$\epsilon n$

Untuk makalah asli, jelas dan ditulis dengan baik, lihat Bernard Chazelle, The Soft Heap: Antrian Prioritas Perkiraan dengan Tingkat Kesalahan Optimal, Jurnal ACM, 47 (6), hlm. 1012-1027, 2000 . Untuk implementasi dan analisis alternatif yang mengklaim lebih sederhana dan lebih intuitif dari SODA'09, lihat Kaplan H. & Zwick U., Implementasi yang lebih sederhana dan analisis tumpukan lunak Chazelle, 2009 .

Oke, akhirnya membuat Anda kompleksitas yang Anda cari, dan apa yang terbaik, saya menemukannya dalam literatur:

Kompleksitas Kasus Terburuk

Hapus :$\bf\mathcal{O}(1)$

Hapus-min :$\bf\mathcal{O}(1)$

Cari-mnt :$\bf\mathcal{O}(1)$

Sisipkan :$\bf\mathcal{O}(log\ n)$

Referensi

JIKA MELD diizinkan untuk mengambil waktu linier, dimungkinkan untuk mendukung DELETE-MIN dalam waktu konstan kasus terburuk dengan menggunakan pohon pencarian jari Dietz dan Raman [3]. Dengan menggunakan struktur data mereka MAKEQUEUE , FINDMIN , DELETEMIN , DELETE dapat didukung dalam waktu kasus terburuk , INSERT dalam waktu kasus terburuk dan MELD dalam waktu kasus terburuk .$\mathcal{O}(1)$$\mathcal{O}(log\ n)$$\mathcal{O}(n)$

Brodal, Gerth Stølting. 'Antrian Prioritas yang Dapat Dicetak Cepat'. Dalam Prosiding Lokakarya Internasional ke-4 tentang Algoritma dan Struktur Data, 282–290. Gumpalan '95. London, Inggris, Inggris: Springer-Verlag, 1995.

[3]: Dietz, Paul F, dan Rajeev Raman. 'Pohon Pembaruan Waktu Pencarian Jari yang Konstan'. Pemrosesan Informasi Surat 52, no. 3 (1994): 147 - 154.

Meskipun ini menggunakan model perhitungan RAM :

Struktur data kami menggunakan model mesin akses-acak (RAM) dengan ukuran biaya unit dan ukuran kata logaritmik;

Baru-baru ini, model komputasi Pointer-Machine telah diberikan [1].

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, dan Kostas Tsichlas. 'Pohon Pencarian Jari Optimal di Mesin Pointer'. J. Comput. Syst. Sci. 67, tidak. 2 (September 2003): 381-418.

Mendekati masalah ini dengan mempertahankan dua struktur data: Array dan Binary Tree.

Untuk mempertahankan pengindeksan dalam array, sebelumnya Anda memiliki ; tetapi baru-baru ini telah diatasi dengan memodifikasi analisis dari teknik kronogram. Ikatan [bawah] baru telah terbukti untuk masalah yang serupa dalam model probe-sel 1 . Dari membaca artikel itu; itu adalah pemahaman saya bahwa terikat berlaku untuk masalah representasi daftar juga.$\Omega(\dfrac{\log n}{\log\log n})$$\Omega(\log n)$

Sekarang jika Anda memasukkan pohon biner ke dalam array Anda dan menyeimbangkan kembali + reindex setiap pembaruan , maka Anda akan memiliki: kompleksitas.$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

Jangka waktu terpanjang Anda — lebih dari nullelemen yang dihapus — akan menjadi . Ini jelas tidak meninggalkan keuntungan teoritis atas penyeimbangan ulang + pengindeksan ulang setiap pembaruan.$\mathcal{O}(\log n)$

Bergantung pada distribusi Anda, Anda dapat membuat asumsi untuk hanya menyeimbangkan kembali setiap insert; sehingga menarik kompleksitas dari ekstrak. Ekstrak — dari kedua ujungnya - hanya akan mengambil ; karena tidak perlu reindex (lacak saja indeks offset untuk menyimpannya di ).$\mathcal{O}(1)$$\mathcal{O}(1)$

Jika Anda tidak dapat membuat asumsi itu, mereka pendekatan saya akan meninggalkan Anda dengan memasukkan, menyeimbangkan, dan mengekstrak. Itu memang memiliki keunggulan dibandingkan beberapa pendekatan lain, di mana Anda bisa mendapatkan min / max dan di mana saja di antara - misalnya: beri saya nilai median - dalam . Selain itu memang memiliki fungsionalitas.$\mathcal{O}(\log n)$$\mathcal{O}(1)$delete_at(idx)

1 Patrascu, Mihai, dan Erik D. Demaine. "Batas Bawah Logaritmik dalam Model Sel-Probe." SIAM J. Comput. 35, tidak. 4 (April 2006): 932–963. doi: 10.1137 / S0097539705447256.

Temukan-mnt dalam dengan waktu pembaruan yang diharapkan dari$O(1)$$O(\sqrt{log\text{ }log\text{ }n})$

Lihat makalah 2007: Kesetaraan antara antrian prioritas dan pengurutan oleh Mikkel Thorup.

Catatan: Ia merujuk ke artikel 2002 oleh Han & Thorup: Integer Sorting dalam Waktu yang Diharapkan dan Ruang Linier$O(n\text{ }\sqrt{log\text{ }log\text{ }n})$ .

Analisis

Sisipkan :$\mathcal{o}(n\ log\ log\ n)$

Cari :$\mathcal{o}(log\ log\ n)$

Hapus :$\mathcal{O}(1)$

Spasi :$\mathcal{O}(n)$

Get-Min :$\mathcal{O}(1)$

Extract-Min :$\mathcal{O}(1)$

Penerapan

1. Bentuk daftar dari sejumlah elemen yang sewenang-wenang (konstan), katakanlah 6:$\mathcal{O}(1)$
2. Sortir daftar: =$\mathcal{O}(6)$$\mathcal{O}(1)$
3. Titik penyisipan untuk setiap simpul berikutnya , akan menjadi elemen kedua (') pos (-1 untuk <, +1 untuk> dan dengan dua args tergantung pada mana Anda mulai / selesai di: dan akan ditemukan menggunakan Interpolasi Dinamis Cari [1] di:$k$$\pm$ $$((k > n_{\text{size}-1}) \lor (k<n_{0}) \lor ((k<n_{i}) \land (k>n_{i+1})))$$ $\mathcal{o}(log\ log\ n)$

[1]: Andersson, Arne, dan Christer Mattsson. 'Pencarian Interpolasi Dinamis dalam O (log log n) Waktu'. Dalam Automata, Bahasa dan Pemrograman, diedit oleh Andrzej Lingas, Rolf Karlsson, dan Svante Carlsson, 700: 15–27. Catatan Kuliah di Ilmu Komputer. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58 .