A Sterta jest wyjątkowy kompletne drzewo binarne . Ponieważ sterta jest kompletnym drzewem binarnym, sterta zawiera N węzły mają log N wysokość. Przydatne jest usunięcie elementu o najwyższym lub najniższym priorytecie. Zwykle jest przedstawiany jako szyk . Istnieją dwa rodzaje stert w plikuMin-Sterta
W Min-Sterta klucz obecny w węźle głównym musi być mniejszy lub równy spośród kluczy obecnych u wszystkich jego dzieci. Ta sama właściwość musi być rekurencyjnie prawdziwa dla wszystkich poddrzew w tym drzewie binarnym. W Min-Heap minimalny kluczowy element obecny w katalogu głównym. Poniżej znajduje się drzewo binarne, które spełnia wszystkie właściwości Min Heap.
Maksymalna sterta
W Maksymalny stos klucz obecny w węźle głównym musi być większy lub równy spośród kluczy obecnych u wszystkich jego dzieci. Musi być ta sama nieruchomość rekurencyjnie PRAWDA dla wszystkich poddrzew w tym drzewie binarnym. W Max-Heap maksymalny kluczowy element obecny w katalogu głównym. Poniżej znajduje się drzewo binarne, które spełnia wszystkie właściwości Max Heap.
Różnica między stertą minimalną a stertą maksymalną
| Min. sterta | Maksymalna sterta | |
|---|---|---|
| 1. | W Min-Heap klucz obecny w węźle głównym musi być mniejszy lub równy spośród kluczy obecnych u wszystkich jego dzieci. | W Max-Heap klucz obecny w węźle głównym musi być większy lub równy spośród kluczy obecnych u wszystkich jego dzieci. |
| 2. | W Min-Heap minimalny kluczowy element obecny w katalogu głównym. | W Max-Heap maksymalny kluczowy element obecny w katalogu głównym. |
| 3. | Min-Heap używa rosnącego priorytetu. | Max-Heap używa malejącego priorytetu. |
| 4. | W konstrukcji Min-Heap priorytet ma najmniejszy element. | W konstrukcji Max-Heap priorytet ma największy element. |
| 5. | W Min-Heap najmniejszy element jest pierwszym, który zostanie wyrzucony ze sterty. | W Max-Heap największy element jest pierwszym, który zostanie wyrzucony ze sterty. |
Zastosowania stosów :
- Sortowanie sterty : Heap Sort to jeden z najlepszych algorytmów sortowania, jakie wykorzystują Kopia binarna Do posortować tablicę W O(N*log N) czas.
- Kolejka priorytetowa : Kolejkę priorytetową można zaimplementować przy użyciu sterty, ponieważ obsługuje ona wstawić() , usuwać() , wyodrębnijMax() , zmniejszKlucz() operacje w O(log N) czas.
- Najkrótsza ścieżka Dijkstry I Minimalne drzewo rozpinające Prima .
Analiza wydajności Min-Heap i Max-Heap :
- Uzyskaj element maksymalny lub minimalny: O(1)
- Wstaw element do sterty Max-Heap lub Min-Heap: O(log N)
- Usuń element maksymalny lub minimalny: O(log N)