Spisu treści:
Definicja - Co oznacza Heap?
Kupa, w kontekście struktury danych, jest drzewną strukturą danych, która spełnia właściwość kupy, w której każdemu elementowi przypisana jest wartość klucza lub waga. Klucz o niższej wartości zawsze ma węzeł nadrzędny z kluczem o wyższej wartości. Nazywa się to strukturą stosu maksymalnego i spośród wszystkich węzłów węzeł główny ma najwyższy klucz.
Czasami struktura oparta na drzewach ma zasadę odwróconej struktury, w której element z kluczem o wyższej wartości zawsze ma klucz o niższej wartości jako węzeł nadrzędny. Nazywa się to strukturą stosu min i spośród wszystkich węzłów węzeł główny ma najniższy klucz.
Techopedia wyjaśnia Heap
Nie ma praktycznych ograniczeń co do liczby dzieci, które każdy węzeł może mieć na stosie, nawet jeśli każdy węzeł ma zwykle najwyżej dwoje. Sterta jest uważana za najbardziej wydajną implementację abstrakcyjnego typu danych, znanego jako kolejka priorytetowa. Implementacja stosu jest niezbędna w różnych algorytmach graficznych (w tym algorytmie Dijkstry), a także w algorytmie sortowania stosów.
Sterty mają kilka wariantów, które działają z wysoką wydajnością jako abstrakcyjne implementacje kolejki priorytetowej typu danych. Wiele aplikacji, takich jak algorytmy grafowe, wymaga implementacji kolejek priorytetowych.
Tablica jest najczęstszą formą implementacji sterty, w której nie są potrzebne wskaźniki do łączenia jej elementów.
Sterty wykonują wiele operacji, w tym:
- Find-max: wyszukuje najwyższy kluczowy węzeł wśród grupy węzłów
- Find-min: wyszukuje najniższy kluczowy węzeł wśród grupy węzłów
- Delete-max: Usuwa najwyższy kluczowy węzeł wśród grupy węzłów
- Delete-min: Usuwa najniższy kluczowy węzeł wśród grupy węzłów
Sterty obejmują również funkcje, które wykonują scalanie, wstawianie i zmiany klawiszy.
Ta definicja została napisana w kontekście struktury danych
