Dlaczego większość języków zapewnia implementację stosu minimalnego zamiast stosu maksymalnego?

19

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ę

design algorithms

— Bernardo Pires
źródło

Czyż nie są dokładnie tym samym? Głosuję za zamknięciem jako argumentujący.

2

Zaledwie kilka dni temu potrzebowałem minimalnej sterty w C ++ i byłem trochę zirytowany tym, że priorytet_queue domyślnie ustawiony jest na maksymalną stertę. Zmusiło mnie to do zdefiniowania operatora> w mojej klasie niestandardowej, która już miała operatora <. Podczas pracy z wykresami zazwyczaj chcesz nadać priorytet najkrótszym krawędziom, więc potrzebujesz minimalnego stosu.

— LaC

2

@LaC: możesz użyć std::not2(std::less<T>()).

9

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.

— ślamazara
źródło

2

Zwykle programuję w C ++ i zastanawiam się wręcz przeciwnie: dlaczego C ++ nie implementuje min-sterty? Jak powiedziałeś, większość algorytmów używa min-sterty.

— Martín Fixman

5

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.

3

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.

— LiKao
źródło

3

Nie sądzę, żeby istniało takie połączenie. Możesz zaimplementować dowolny rodzaj sterty za pomocą <lub>. Rzeczywiście, std :: less jest domyślnym w STL, ale implementują maksymalną stertę zamiast sterty minimalnej.

— LaC

1

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.

— Daniel R. Hicks
źródło