Kiedy chciałbym użyć sterty?

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

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.

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.

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!

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

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

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