Właśnie coś zauważyłem i zastanawiam się, czy jest jakiś powód tego. Z wyjątkiem C ++ (std :: priorytet_queue jest stertą maksymalną), nie znam żadnego innego języka, który oferuje stertę maksymalną.
Moduł heapq Pythona implementuje binarną mini-stertę na szczycie listy.
Biblioteka Java zawiera klasę PriorityQueue, która implementuje kolejkę o minimalnym priorytecie.
Biblioteka Go zawiera moduł kontenera / sterty, który implementuje minimalną stertę nad dowolną kompatybilną strukturą danych.
Podstawa Apple Core Foundation zawiera strukturę CFBinaryHeap, która implementuje mini-stertę.
Uważam, że maksymalny stos jest bardziej intuicyjny niż minimalny stos i uważam, że technicznie różnica w implementacji jest tylko kwestią zmiany operatora porównania. Czy jest jakiś prawdziwy powód? Większość aplikacji potrzebuje min zamiast maksymalnej sterty? Z góry dziękuję
źródło
std::not2(std::less<T>()).Odpowiedzi:
Jak zauważyli inni, jeśli kupa akceptuje komparator, to nie jest zbyt trudne do uzyskania jednego lub drugiego zachowania. Szybkie przejrzenie kodu Google sugeruje jednak, że min-stos jest zdecydowanie bardziej rozpowszechniony w rzeczywistym kodzie, z powodu dwóch aplikacji, które pojawiają się wielokrotnie.
Dijkstra / A * / wiele innych algorytmów najkrótszej ścieżki (ponieważ ścieżki częściowe stają się dłuższe).
Symulacja zdarzenia (ponieważ czas płynie do przodu).
Argumentowałbym również, że ponieważ sortowanie domyślne zwraca elementy od małych do dużych, podobnie powinna być domyślna sterta.
źródło
To tylko kwestia gustu. Nie sądzę, że będzie jakiś konkretny powód. To tak, jak niektórzy ludzie lubią wyrażać problemy związane z optymalizacją jako minimalizowanie kosztów, podczas gdy inni lubią maksymalizować zysk.
źródło
Większość języków, które znam, pozwalają na przekazanie parametru decydującego o tym, czy ma on być stertą minimalną, czy maksymalną. Tak więc wartość domyślna jest nieco dowolna. Wydaje mi się, że w przypadku większości języków określenie domyślnego operatora jest kwestią spójności. Dla C ++ w STL domyślnie
std::lessprowadzi do mini-sterty.Spójność korzystania
std::lessz domyślnych ustawień wszędzie oznacza, że musisz wdrożyć to porównanie tylko wtedy, gdy używasz jakiejkolwiek struktury danych i nie musisz decydować, która struktura danych będzie używana później podczas projektowania klas. Sądzę, że jest tak samo w przypadku innych języków, z tą różnicą, że standardem jest porównanie większe niż porównanie.źródło
Zasadniczo wartość indeksu jest liczbą dowolną. Jeśli uważasz, że liczba reprezentuje priorytet, a większe liczby są wyższymi priorytetami, wówczas sensowne jest użycie stosu maksymalnego. Ale jeśli liczby reprezentują np. Koncepcyjne liczby piekarnicze („Weź liczbę”), wówczas stos minimalny ma większy sens.
Zawsze możesz dokonać konwersji z jednego na drugi, biorąc uzupełnienie indeksu 1.
źródło