Perbedaan antara tumpukan dan antrian prioritas

36

Saya selalu berpikir bahwa tumpukan dan antrian prioritas adalah sinonim - struktur data abstrak yang mendukung insert, findMindan deleteMinoperasi.

Beberapa literatur tampaknya setuju dengan saya - Struktur Data Murni Fungsional Chris Okasaki (bab 3), misalnya.

Di sisi lain, halaman tumpukan Wikipedia mendefinisikannya sebagai struktur data berbasis pohon, dan menyatakan bahwa tumpukan adalah implementasi konkret dari antrian prioritas.

Saya mengalami kesulitan mendamaikan ini dengan fakta bahwa saya dapat memikirkan lebih dari satu implementasi tumpukan - tumpukan kiri, tumpukan binomial, tumpukan hamparan ...

Apakah fakta sederhana bahwa tumpukan dapat diimplementasikan dengan struktur data yang berbeda tidak berarti, menurut definisi, bahwa itu adalah struktur data abstrak? Dan jika itu masalahnya, apakah ada perbedaan aktual dengan antrian prioritas?

data-structures Nicolas Rinaudo
sumber
11
Baca halaman Wikipedia tentang antrian prioritas ( en.wikipedia.org/wiki/Priority_queue ), ia mengatakan "antrian prioritas dapat diimplementasikan dengan tumpukan atau berbagai metode lain seperti array yang tidak berurutan" - dan itu sebenarnya jawaban untuk pertanyaanmu.
Doc Brown
2
Yah, tidak juga - itu tidak membantu saya memahami apakah tumpukan adalah struktur data yang konkret atau abstrak. Saya cenderung mengatakan yang abstrak, karena ada banyak implementasi konkret dari tumpukan. Jika itu yang terjadi, dan daftar prioritas dan tumpukan keduanya struktur data abstrak dengan sifat yang sama, maka saya perlu bantuan memahami perbedaannya, dan mengatakan bahwa satu adalah kemungkinan implementasi yang lain tidak akan sangat membantu jika tidak ada yang sebenarnya merupakan implementasi konkret.
Nicolas Rinaudo
Hal-hal bahkan lebih buruk: tumpukan biner dapat diimplementasikan sebagai array atau sebagai pohon biner. Untungnya, saya belum pernah mendengar tentang array yang diimplementasikan sebagai sesuatu yang lain.
Alexey

Jawaban:

25

Antrian prioritas dapat memiliki implementasi apa pun, seperti larik yang Anda cari secara linear ketika Anda muncul. Semua itu berarti bahwa ketika Anda pop Anda mendapatkan nilai dengan minimum atau maksimum tergantung.

Tumpukan klasik seperti yang biasanya disebut biasanya tumpukan kecil. Implementasi yang memiliki kompleksitas waktu yang baik ( O(log n)on push dan pop) dan tidak ada memori overhead.

ratchet freak
sumber
4
Apakah Anda bermaksud mengatakan bahwa perbedaan adalah bahwa sementara mereka berbagi operasi yang sama ( findMin, deleteMin, insert), tumpukan telah dijamin "baik" kompleksitas bagi mereka di mana antrian prioritas tidak?
Nicolas Rinaudo
Tidak bisakah heap juga memiliki implementasi yang berbeda dengan kompleksitas waktu yang berbeda (misalnya pohon biner yang ditautkan)? Juga, kompleksitas waktu tergantung pada memori yang digunakan. Jika itu adalah pita magnetik, tidak akan ada O(log(n))dorongan dan pop, kurasa.
Alexey
6

Situs web ini memberikan penjelasan yang sangat jelas. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Singkatnya, antrian prioritas dapat diimplementasikan menggunakan banyak dari struktur data yang telah kita pelajari (array, daftar tertaut, atau pohon pencarian biner). Namun, struktur data tersebut tidak memberikan operasi yang paling efisien. Untuk menjadikan semua operasi sangat efisien, kami akan menggunakan struktur data baru yang disebut heap.

Chihung Yu
sumber
1
Perhatikan bahwa pada ringkasan halaman yang Anda tautkan, antrian prioritas itu sendiri disebut struktur data .
Alexey
2

Saya pikir apa yang Anda tulis tentang beton vs abstrak benar. Di mana Anda mengatakan bahwa tumpukan tumpukan, tumpukan binomial adalah implementasi dari tumpukan yang berbeda, saya pikir lebih tepat untuk mengatakan bahwa mereka adalah jenis tumpukan yang berbeda. Heap saya anggap sebagai kategori implementasi yang umumnya menjamin tidak hanya antarmuka yang sama, tetapi juga waktu akses yang sama.

Anda melihat ini dengan peta asosiatif, dan tabel hash dan pohon pencarian biner juga. Bsts dan tabel hash keduanya struktur data konkret yang menyediakan antarmuka abstrak peta asosiatif. Pohon merah-hitam dan dan pohon-pohon AVL keduanya seimbang, dengan jaminan O besar yang sama dan antarmuka tambahan yang sama (dalam urutan traversal). Mereka adalah jenis pohon yang berbeda, menurut saya lebih dari sekadar implementasi pohon yang berbeda. Mereka adalah implementasi yang berbeda tetapi terkait erat dari peta asosiatif.

Nir Friedman
sumber