Różnica między stertą a kolejką priorytetową

36

Zawsze myślałem, że stosy i kolejki priorytetowe były synonimami - streszczenie struktura danych, która wspiera insert, findMini deleteMinoperacje.

Wygląda na to, że część literatury jest ze mną zgodna - na przykład struktury danych funkcjonalne Chrisa Okasakiego (rozdział 3).

Z drugiej strony strona sterty Wikipedii definiuje ją jako strukturę danych opartą na drzewach i stwierdza, że ​​sterty są konkretną implementacją kolejek priorytetowych.

Trudno mi to pogodzić z faktem, że mogę wymyślić więcej niż jedną implementację stosu - stosy lewicowe, stosy dwumianowe, stosy rozrzucone ...

Czy prosty fakt, że stertę można wdrożyć przy użyciu różnych struktur danych, nie oznacza z definicji, że jest to abstrakcyjna struktura danych? A jeśli tak, to czy rzeczywiście istnieje różnica w stosunku do kolejek priorytetowych?

data-structures Nicolas Rinaudo
źródło
11
Przeczytaj stronę Wikipedii na temat kolejek priorytetowych ( en.wikipedia.org/wiki/Priority_queue ), napisano, że „kolejka priorytetowa może zostać zaimplementowana za pomocą stosu lub różnych innych metod, takich jak nieuporządkowana tablica” - i to właściwie odpowiedź na Twoje pytanie.
Doc Brown
2
Cóż, niezupełnie - nie pomaga mi zrozumieć, czy sterta jest konkretną strukturą danych czy abstrakcyjną. Powiedziałbym, że jest to abstrakcja, ponieważ istnieje wiele konkretnych implementacji stosu. Jeśli tak jest, a lista priorytetów i sterta są abstrakcyjnymi strukturami danych o tych samych właściwościach, potrzebuję pomocy w zrozumieniu różnicy, a powiedzenie, że jedna jest możliwa implementacja drugiej, nie jest szczególnie pomocne, jeśli żadna z nich nie jest konkretne wdrożenie.
Nicolas Rinaudo
Jest jeszcze gorzej: kupa binarna może być zaimplementowana jako tablica lub drzewo binarne. Na szczęście nie słyszałem jeszcze o tablicy zaimplementowanej jako coś innego.
Alexey,

Odpowiedzi:

25

Kolejka priorytetowa może mieć dowolną implementację, na przykład tablicę, która jest przeszukiwana liniowo podczas otwierania. Wszystko to oznacza, że ​​kiedy pop wyskakuje, dostajesz wartość z minimum lub maksimum w zależności.

Klasyczna sterta, jak się zwykle nazywa, to zwykle sterta minimalna. Implementacja, która charakteryzuje się dużą złożonością czasu ( O(log n)w trybie push i pop) i nie ma narzutu pamięci.

maniak zapadkowy
źródło
4
Czy chcesz powiedzieć, że różnica jest taka, że podczas gdy te same operacje ( findMin, deleteMin, insert), hałdy są gwarantowane „dobre”, gdzie złożoność dla nich kolejek priorytetowych nie?
Nicolas Rinaudo,
Czy sterty nie mogą mieć także różnych implementacji o różnej złożoności czasowej (na przykład zwykłe połączone drzewo binarne)? Również złożoność czasu zależy od używanej pamięci. Jeśli jest to taśma magnetyczna O(log(n)), przypuszczam , że nie będzie możliwości push i pop.
Alexey,
6

Ta strona internetowa zawiera naprawdę jasne wyjaśnienie. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Krótko mówiąc, kolejka priorytetowa może zostać zaimplementowana przy użyciu wielu struktur danych, które już zbadaliśmy (tablica, lista połączona lub drzewo wyszukiwania binarnego). Jednak te struktury danych nie zapewniają najbardziej wydajnych operacji. Aby wszystkie operacje były bardzo wydajne, zastosujemy nową strukturę danych zwaną stertą.

Chihung Yu
źródło
1
Zauważ, że w podsumowaniu strony, do której linkujesz, sama kolejka priorytetowa nazywa się strukturą danych .
Alexey
2

Myślę, że to, co napisałeś o konkretach kontra abstrakcjach, jest poprawne. Kiedy mówisz, że stosy rozrzucone, stosy dwumianowe są różnymi implementacjami stosów, myślę, że bardziej słuszne jest stwierdzenie, że są to różne typy stosów. Sterta uważam za kategorię implementacji, która ogólnie gwarantuje nie tylko ten sam interfejs, ale także takie same czasy dostępu.

Widzisz to w mapach asocjacyjnych, tabelach skrótów i drzewach wyszukiwania binarnego. Tabele skrótów i tabele skrótów są konkretnymi strukturami danych, które zapewniają interfejs abstrakcyjny mapy asocjacyjnej. Czerwone czarne drzewa i drzewa avl to zrównoważone bst, z tymi samymi dużymi gwarancjami O i tym samym dodatkowym interfejsem (w celu przejścia). Są to różne rodzaje drzew, powiedziałbym więcej niż różne implementacje drzew. Są to różne, ale ściśle powiązane implementacje map asocjacyjnych.

Nir Friedman
źródło