Kiedy chciałbym użyć sterty?

92

Oprócz oczywistej odpowiedzi w postaci kolejki priorytetowej, kiedy stos byłby przydatny w moich przygodach z programowaniem?

Mithrax
źródło
8
Jest tu mnóstwo dobrych odpowiedzi, więc dodam „kiedy stos nie jest wystarczająco duży”.
Don Werve,

Odpowiedzi:

121

Używaj go, gdy potrzebujesz szybkiego dostępu do największego (lub najmniejszego) elementu, ponieważ ten element zawsze będzie pierwszym elementem w tablicy lub w korzeniu drzewa.

Jednak pozostała część tablicy jest częściowo nieposortowana. W ten sposób natychmiastowy dostęp jest możliwy tylko do największego (najmniejszego) elementu. Wstawianie jest szybkie, więc jest to dobry sposób radzenia sobie z nadchodzącymi zdarzeniami lub danymi i zawsze masz dostęp do najwcześniejszych / największych.

Przydatne w przypadku kolejek priorytetowych, harmonogramów (gdzie pożądany jest najwcześniejszy element) itp.

Sterta to drzewo, w którym wartość węzła nadrzędnego jest większa niż wartość dowolnego z jego węzłów podrzędnych.

Jeśli pomyślisz o sterty jako o drzewie binarnym przechowywanym w liniowej kolejności według głębokości, z węzłem głównym na początku (potem potomkami tego węzła, a następnie dziećmi tych węzłów); wtedy dzieci węzła o indeksie N mają 2N + 1 i 2N + 2. Ta właściwość umożliwia szybki dostęp według indeksu. A ponieważ sterty są manipulowane przez zamianę węzłów, umożliwia to sortowanie na miejscu.

Joe Koberg
źródło
3
Należy również pamiętać, że może to być wygodne, gwarantowane sortowanie NlogN, które nie wymaga dodatkowych alokacji tablic
Overflown
38
Wspaniale jest też znać mnóstwo pytań do wywiadów;)
vivekian2
21
@ vivekian2 Jedynym powodem, dla którego tu jestem, jest to, że zaraz udzielę wywiadu.
byxor
dlaczego nie użyć klasy stosu ze stosem pomocniczym do śledzenia największego (lub najmniejszego) elementu. pobieranie jest O (1)
Ridhwaan Shakeel
@RidhwaanShakeel Jeśli używasz stosu, twój przedmiot zawsze będzie umieszczony na głowie, co jeśli pozycja przedmiotu musi zostać określona na podstawie jakiejś właściwości przedmiotu, takiej jak największe wydarzenie (na podstawie liczby osób biorących udział w wydarzeniu).
SandeepGodara
49

Hapy to konstrukcje mające na celu umożliwienie szybkiego dostępu do min lub max .

Ale dlaczego chcesz tego? Możesz po prostu sprawdzić każdy wpis w dodatku, aby zobaczyć, czy jest najmniejszy, czy największy. W ten sposób zawsze masz najmniejszy lub największy w stałym czasie O(1).

Odpowiedź jest taka, ponieważ sterty pozwalają ci wyciągnąć najmniejszy lub największy i szybko poznać NASTĘPNY najmniejszy lub największy . Dlatego nazywa się to kolejką priorytetową.

Przykład z prawdziwego świata (choć niezbyt uczciwy świat):

Załóżmy, że masz szpital, do którego trafiają pacjenci na podstawie ich wieku. Najstarsi są zawsze obecni jako pierwsi, bez względu na to, kiedy stanął w kolejce.

Nie możesz po prostu śledzić najstarszego, ponieważ jeśli go wyciągniesz, nie znasz następnego najstarszego. Aby rozwiązać ten problem szpitala, wdrażasz maksymalny stos . Ta sterta jest z definicji częściowo uporządkowana. Oznacza to, że nie możesz sortować pacjentów według ich wieku, ale wiesz, że najstarsze są zawsze na górze, więc możesz wyciągnąć pacjenta w ciągłym czasie O(1)i ponownie zrównoważyć stos w czasie dziennika O(log N).

Bardziej wyrafinowany przykład:

Załóżmy, że masz sekwencję liczb całkowitych i chcesz śledzić plik median. Mediana to liczba znajdująca się w środku uporządkowanej tablicy.

Przykład:

[1, 2, 5, 7, 23, 27, 31]

W powyższym przypadku 7jest to mediana, ponieważ tablica zawierająca mniejsze liczby [1, 2, 5]ma taki sam rozmiar jak tablica zawierająca większe liczby [23, 27, 31]. Zwykle, jeśli tablica ma nieparzystą liczbę elementów, mediana jest średnią arytmetyczną dwóch elementów pośrodku, np (5 + 7)/2.

A teraz, jak możesz śledzić medianę? Mając 2 stosy , jeden minimalny stos zawierający liczby mniejsze niż bieżąca mediana i maksymalny stos zawierający liczby większe niż bieżąca mediana. Teraz, jeśli te sterty są zawsze zrównoważone, 2 sterty będą zawierały taką samą liczbę elementów lub jeden będzie miał o 1 element więcej niż drugi, najwięcej.

Kiedy dodajesz nowy element do sekwencji, jeśli liczba jest mniejsza niż bieżąca mediana, dodajesz go do sterty minimalnej, w przeciwnym razie dodajesz ją do sterty maksymalnej. Teraz, jeśli sterty są niezrównoważone (jedna sterta ma więcej niż 1 element więcej niż druga), wyciągasz element z największego stosu i dodajesz do najmniejszego. Teraz są zrównoważone.

André Pena
źródło
6
Bardziej wyrafinowany przykład jest niesamowity! Na pewno kiedyś tego spróbuję. Myślę jednak, że w twoim przykładzie jest mały błąd. Ponieważ musimy uzyskać medianę, uśredniając dwa elementy w środku. Zakładam, że musimy użyć sterty minimalnej do przechowywania liczb większych niż bieżąca mediana i sterty maksymalnej do przechowywania liczb mniejszych niż bieżąca mediana. W ten sposób możemy wyodrębnić dwa elementy w środku w stałym czasie i obliczyć medianę? Mam rację?
Calvin Ku
12

Cechą charakterystyczną sterty jest to, że jest to struktura, która utrzymuje dane na wpół uporządkowane; jest to więc dobry kompromis między kosztem utrzymania pełnego porządku a kosztem przeszukiwania przypadkowego chaosu. Ta cecha jest używana w wielu algorytmach, takich jak selekcja, porządkowanie czy klasyfikacja.

Inną użyteczną cechą sterty jest to, że można ją utworzyć na miejscu z tablicy!

AticusFinch
źródło
3

Dobry również dla algorytmów selekcji (znajdowanie min lub max)

Dan
źródło
3

w każdej chwili podczas sortowania tymczasowej listy należy wziąć pod uwagę stosy.

Javier
źródło
0

Możesz użyć minHeap lub maxHeap, jeśli chcesz uzyskać dostęp odpowiednio do najmniejszych i największych elementów.

QuadBiker
źródło