Struktur data yang efisien mendukung Sisipan, Hapus, dan MostFrequent

Anggaplah kita memiliki himpunan $D$ dan setiap anggota adalah pasangan data dan kunci. Kami menginginkan struktur data yang akan mendukung operasi berikut:$D$

• Masukkan ke ,$(d,k)$$D$
• Hapus anggota , (tidak perlu mencari untuk menemukan , misalnya menunjuk ke anggota di ),e e $e$$e$$e$$D$
• MostFrequent, yang mengembalikan anggota sehingga adalah salah satu kunci yang paling sering di (perhatikan bahwa kunci yang paling sering tidak perlu unik).e . k e y $e \in D$$e.key$$D$

Apa yang akan menjadi implementasi efisien dari struktur data ini?

Solusi saya adalah tumpukan untuk kunci dan frekuensi mereka diprioritaskan oleh frekuensi ditambah tabel hash di mana fungsi hash memetakan anggota dengan kunci yang sama ke slot yang sama di tabel hash (dengan pointer dari masing-masing bagian ke yang lain).

Ini dapat memberikan untuk dua operasi pertama dan untuk yang ketiga (waktu menjalankan kasus terburuk).Θ ( 1 $\Theta(\lg n)$$\Theta(1)$

Saya bertanya-tanya apakah ada solusi yang lebih efisien? (atau solusi yang lebih sederhana dengan efisiensi yang sama?)

Dalam model perhitungan berbasis perbandingan, Anda dapat menerapkan antrian prioritas menggunakan tumpukan Fibonacci alih-alih tumpukan biasa. Ini akan memberi Anda batas berikut: waktu diamortisasi untuk memasukkan dan O ( log n ) waktu diamortisasi untuk operasi penghapusan.$\mathcal{O}(1)$$\mathcal{O}(\log n)$

Jika Anda berangkat dari model berbasis perbandingan dan mengadopsi model RAM di mana kunci dianggap sebagai string biner, masing-masing berisi satu atau lebih kata-kata mesin, Anda dapat mengimplementasikan antrian prioritas Anda di . Memang, Anda dapat mencapai untuk menyisipkan dan menghapus operasi O ( $o(\log n)$danO(1)waktu untuk operasi findMin. Thorup membuktikannya$\mathcal{O}(\sqrt{\log \log n})$$\mathcal{O}(1)$

Jika kita dapat mengurutkan kunci dalam waktu S ( n ) per kunci, maka kita dapat mengimplementasikan antrian prioritas yang mendukung pencarian-min dalam waktu konstan dan pembaruan (masukkan dan hapus) dalam waktu S ( n ) .$n$$S(n)$$S(n)$

Lihat M. Thorup. Kesetaraan antara antrian prioritas dan pengurutan, 2002. di Proc. FOCS 2002

Karena kita dapat mengurutkan dalam waktu yang diharapkan dan ruang linear, seperti yang ditunjukkan oleh$\mathcal{O}(n \sqrt{\log \log n})$

Y. Han dan M. Thorup. Sortasi integer dalam waktu yang diharapkan dan ruang linear. dalam Proc. FOCS 2002$\mathcal{O}(n \sqrt{\log \log n})$

ikatan terbukti.

Anda dapat melakukan semua ini dalam perkiraan waktu diamortisasi. Trik penting adalah bahwa kita tidak memerlukan kekuatan penuh dari antrian prioritas, karena frekuensi kunci hanya berubah sebesar 1 selama setiap penyisipan atau penghapusan.$O(1)$

Solusi saya di bawah ini benar-benar hanya solusi Anda dengan antrian prioritas "tidak efisien" yang berfungsi dengan baik untuk kasus ini: antrian prioritas maksimum diimplementasikan sebagai daftar ember kunci yang tertaut ganda memiliki O (1) insertMin, deleteMax, removeFromBucket, dan tingkatkan kunci.

Menyimpan daftar Bucket yang tertaut ganda, di mana setiap Bucket memiliki kumpulan kunci hash yang tidak kosong (yang akan saya sebut Cohort) dan bilangan bulat positif (yang saya sebut ValCount). Dalam Bucket b, setiap kunci k dalam Cohort of b memiliki jumlah nilai unik yang sama dengan yang ada dalam set yang Anda pertahankan. Misalnya, jika set Anda memiliki pasangan (a, apel), (a, alpukat), (b, pisang), (c, mentimun), (d, buah naga) di mana huruf tunggal adalah kunci dan buahnya adalah nilainya, maka Anda akan memiliki dua Bucket: Satu Bucket akan memiliki ValCount 2 dan Cohort yang hanya terdiri dari satu kunci: a. Bucket lainnya akan memiliki ValCount 1 dan Cohort yang terdiri dari tiga kunci b, c, dan d.

Daftar Bucket yang tertaut ganda harus tetap dipesan oleh ValCount. Penting bahwa kita dapat menemukan kepala dan ekor daftar dalam waktu dan bahwa kita dapat menyambungkan dalam Bucket baru dalam waktu O ( 1 ) jika kita tahu tetangganya. Secara tidak imajinatif, saya akan menyebut daftar Bucket BucketList.$O(1)$$O(1)$

Selain BucketList, kita membutuhkan SetMap, yang merupakan kunci pemetaan peta hash untuk ValueBuckets. ValueBucket adalah pasangan yang terdiri dari ValueSet (set nilai hash yang tidak kosong) dan pointer non-null ke Bucket. ValueSet yang terkait dengan kunci k berisi semua nilai unik yang terkait dengan k. Pointer Bucket yang terkait dengan ValueSet memiliki Kohort yang sama dengan ukuran ValueSet. Bucket yang terkait dengan kunci k di SetMap juga dikaitkan dengan kunci k di BucketList.

Dalam C ++:

struct Bucket {
    unsigned ValCount;
    unordered_set<Key> Cohort;
    Bucket * heavier;
    Bucket * lighter;
};
Bucket * BucketListHead;
Bucket * BucketListTail;

struct ValueBucket {
  unordered_set<Value> ValueSet;
  Bucket * bucket;
};
unordered_map<Key, ValueBucket> SetMap;

Untuk menemukan pasangan nilai kunci frekuensi maksimum, kita hanya perlu melihat kepala BucketList, menemukan kunci dalam Cohort, mencari kunci itu di SetMap, dan menemukan nilai dalam ValueSet dari ValueBucket-nya. (Fiuh!)

Memasukkan dan menghapus pasangan nilai kunci lebih sulit.

Untuk menyisipkan atau menghapus pasangan nilai kunci, pertama-tama kita menyisipkan atau menghapusnya di SetMap. Ini akan mengubah ukuran ValueSet, jadi kita perlu memodifikasi Bucket yang terkait dengan kunci tersebut. Satu-satunya Bucket yang perlu kita perhatikan untuk melakukan perubahan ini adalah tetangga terdekat Bucket yang menjadi kuncinya. Ada beberapa kasus di sini, dan mereka mungkin tidak layak dieja sepenuhnya, meskipun saya akan senang untuk menguraikan jika Anda masih mengalami masalah.

Kompleksitas kasus terburuk

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(1)$

$\mathcal{O}(\log \log n)$

$\mathcal{O}(n)$

Bukti

$[0 , N )$ $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$

Yang didirikan dengan kombinasi:

$\tau(n, N)$ $n$$[0 , N)$ $\tau ( n, N ) \le τ ( N, N)$$\tau$

dan:

$n$$[0 , N)$$\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$$q$

Referensi

Thorup, Mikkel. “Antrian Prioritas Integer dengan Penurunan Kunci dalam Waktu Konstan dan Sumber Single Jalur Terpendek.” Dalam Prosiding Simposium ACM Tahunan ke Tiga Puluh Lima tentang Teori Komputasi, 149–158. STOC '03. New York, NY, AS: ACM, 2003.