Pertanyaan Apa struktur data yang benar untuk antrian yang mendukung Min, operasi Max dalam waktu O (1)?


Apa struktur data yang benar untuk antrian yang mendukung operasi Enque, Dequeue, Peak, Min, dan Max dan melakukan semua operasi ini dalam waktu O (1).

Struktur data yang paling jelas adalah daftar yang ditautkan tetapi Min, operasi Max akan menjadi O (n). Antrean Prioritas adalah pilihan sempurna lainnya selain Enqueue, Dequeue harus bekerja dengan cara Antrian yang normal. (FIFO)

Dan opsi lain yang muncul dalam pikiran adalah Heap, tetapi saya tidak dapat cukup memahami bagaimana seseorang dapat mendesain antrean dengan Min, operasi Max menggunakan Heaps.

Bantuan apa pun sangat dihargai.


14
2018-04-16 12:36


asal


Jawaban:


Struktur data yang Anda cari tidak dapat dirancang, jika min () dan max () benar-benar mengubah struktur. Jika min () dan max () mirip dengan peek (), dan menyediakan akses read-only, maka Anda harus mengikuti langkah-langkah dalam pertanyaan ini, tambahkan deque lain yang mirip dengan yang digunakan untuk operasi min () untuk digunakan dalam operasi max (). Sisa dari jawaban ini mengasumsikan bahwa min () dan max () sebenarnya menghapus elemen yang sesuai.

Karena Anda memerlukan enqueue () dan dequeue (), elemen harus ditambahkan dan dihapus dengan urutan kedatangan (FIFO). Antrian double-ended sederhana (baik terhubung atau menggunakan vektor melingkar) akan menyediakan ini dalam O (1).

Tetapi elemen yang akan ditambahkan dapat mengubah min saat ini () dan max (); namun, saat dihapus, nilai min () dan max () lama harus dipulihkan ... kecuali jika dihapus untuk sementara. Pembatasan ini memaksa Anda untuk menjaga elemen disortir entah bagaimana. Setiap struktur pengurutan (min-heap, max-heap, balanced binary tree, ...) akan membutuhkan setidaknya O (log n) untuk menemukan posisi kedatangan baru.

Taruhan terbaik Anda adalah memasangkan pohon biner yang seimbang (untuk min () dan max ()) dengan daftar terkait ganda. Simpul pohon Anda akan menyimpan satu set pointer ke daftar node, diurutkan berdasarkan kunci apa pun yang Anda gunakan dalam min () dan max (). Di Java:

// N your node class; can return K, comparable, used for min() and max() 
LinkedList<N> list;           // sorted by arrival
TreeMap<K,HashMap<N>> tree;   // sorted by K
  • di enque(), Anda akan menambahkan node baru ke akhir list, dan tambahkan simpul yang sama itu, dengan kuncinya, ke HashMap di simpulnya di tree. O (log n).
  • di dequeue(), Anda akan menghapus node dari awal list, dan dari HashMap di simpulnya di pohon. O (log n).
  • di mnt(), Anda akan mencari elemen 1 di pohon. O (1). Jika Anda perlu menghapusnya, Anda memiliki pointer ke daftar tertaut, jadi O (1) di sisi itu; tapi O (log n) untuk menyeimbangkan kembali pohon jika itu adalah elemen terakhir dengan K tertentu.
  • di maks(), logika yang sama berlaku; kecuali bahwa Anda akan mencari elemen terakhir di pohon. Begitu O (log n).
  • di mengintip(), melihat tetapi tidak mengekstrak elemen 1 dalam antrian O (1).

Anda dapat menyederhanakan ini (dengan menghapus HashMap) jika Anda tahu bahwa semua kunci akan unik. Namun, ini tidak berdampak biaya asimtotik: mereka semua akan tetap sama.

Dalam prakteknya, perbedaan antara O (log n) dan O (1)sangat rendah sehingga implementasi peta default di C ++ adalah STL O (log n)-based (Tree bukannya Hash).


6
2018-04-22 11:16



Setiap struktur data yang dapat diambil Min atau Max dalam O (1) waktu perlu menghabiskan setidaknya O (log n) pada setiap Insert dan Remove untuk mempertahankan elemen dalam urutan terurut sebagian. Struktur data yang mencapai ini disebut antrian prioritas.

Antrean prioritas dasar mendukung Insert, Max, dan RemoveMax. Ada beberapa cara untuk membuatnya, tetapi tumpukan biner bekerja paling baik.

Mendukung semua Insert, Min, RemoveMin, Max, dan RemoveMax dengan antrian prioritas tunggal lebih kompleks. Cara untuk melakukan ini dengan struktur data tunggal, diadaptasi dari tumpukan biner, dijelaskan di koran:

Atkinson, Michael D., dkk. "Min-max tumpukan dan antrian prioritas umum."Komunikasi ACM 29.10 (1986): 996-1000.

Ini cepat dan hemat memori, tetapi membutuhkan perawatan yang baik untuk diterapkan dengan benar.


7
2018-04-27 04:22



Struktur ini TIDAK ada!

Ada cara sederhana untuk menyetujui kesimpulan ini.

Seperti yang kita semua tahu, kompleksitas masalah pemilahan adalah O (nlogn). Tetapi jika struktur yang Anda katakan ada, akan ada solusi untuk menyortir:

  1. Enque setiap elemen satu per satu biaya Di)
  2. Dequeue setiap max (atau min) elemen satu per satu biaya Di)

yang berarti masalah pemilahan dapat diselesaikan dengan O (n). Tapi itu MUSTAHIL.


1
2018-04-27 02:50



Asumsi:

bahwa Anda hanya peduli tentang kinerja dan bukan tentang ruang / memori / ...

Sebuah solusi:

Bahwa indeks adalah himpunan, bukan daftar (akan berfungsi untuk daftar, tetapi mungkin membutuhkan tambahan cinta)

Anda bisa melakukan antrean dan tabel hash berdampingan.

Contoh:

Katakanlah pesanannya adalah 5 4 7 1 8 3

Antrian -> 547813

Tabel hash -> 134578

Enqueue:

1) Ambil objek Anda, dan masukkan ke dalam tabel hash di bucket kanan Min / Max akan selalu menjadi indeks pertama dan terakhir. (lihat tabel hash diurutkan)

2) Selanjutnya, masukkan ke antrean Anda seperti biasa.

3) Anda dapat / harus menghubungkan keduanya. Satu ide akan menggunakan nilai tabel hash sebagai penunjuk ke antrian.

Kedua operasi dengan tabel hash besar akan O (1)

Dequeue:

1) Munculkan elemen tinju O (1)

2) hapus elemen dari tabel hash O (1)

Min / Maks:

1) Lihatlah tabel hash Anda. Tergantung pada bahasa yang digunakan, Anda bisa secara teori menemukannya dengan melihat kepala meja, atau ekor meja.

Untuk penjelasan yang lebih baik dari tabel hash yang diurutkan, https://stackoverflow.com/questions/2007212

Catatan: Saya ingin mencatat, bahwa tidak ada struktur data "normal" yang akan melakukan apa yang Anda butuhkan yang saya ketahui. Namun, bukan berarti itu tidak mungkin. Jika Anda akan mencoba untuk menerapkan struktur data, kemungkinan besar Anda harus melakukannya untuk kebutuhan Anda dan tidak akan dapat menggunakan perpustakaan yang tersedia saat ini. Anda mungkin harus melihat menggunakan bahasa tingkat rendah seperti perakitan untuk mencapai ini, tapi mungkin C atau Java mungkin bisa jika Anda baik dengan bahasa-bahasa tersebut.

Semoga berhasil

DIEDIT:   Saya tidak menjelaskan tabel hash yang diurutkan, jadi tambahkan tautan ke SO yang lain untuk menjelaskannya.


-2
2018-04-24 23:02