A Kaudze ir īpašs pilnīgs binārais koks . Tā kā kaudze ir pilnīgs binārs koks, kaudze ar N mezgliem ir žurnāls N augstums. Ir lietderīgi noņemt augstākās vai zemākās prioritātes elementu. Tas parasti tiek attēlots kā masīvs . Ir divu veidu kaudzesMin-Heap
Iekšā Min-Heap saknes mezglā esošajai atslēgai ir jābūt mazākai vai vienādai starp atslēgām, kas atrodas visos tā atslēgās. Tam pašam rekvizītam ir jābūt rekursīvi patiesam visiem šī binārā koka apakškokiem. Min-Heap minimālais galvenais elements, kas atrodas saknē. Zemāk ir Binārais koks, kas apmierina visu Min Heap īpašumu.
Makss kaudze
Iekšā Max-Heap saknes mezglā esošajai atslēgai ir jābūt lielākai par vai vienādai starp atslēgām, kas atrodas visos tā atslēgās. Tam pašam īpašumam jābūt rekursīvi taisnība visiem apakškokiem šajā Binārajā kokā. Max-Heap maksimālais galvenais elements, kas atrodas saknē. Zemāk ir Binārais koks, kas apmierina visas Max Heap īpašības.
Atšķirība starp Min Heap un Max Heap
| Minimālā kaudze | Makss kaudze | |
|---|---|---|
| 1. | Min-Heap atslēgai, kas atrodas saknes mezglā, ir jābūt mazākai vai vienādai ar to atslēgām, kas atrodas visos tā atvasumos. | Max-Heap atslēgai, kas atrodas saknes mezglā, ir jābūt lielākai vai vienādai ar to atslēgām, kas atrodas visos tā atvasumos. |
| 2. | Min-Heap minimālais galvenais elements, kas atrodas saknē. | Max-Heap maksimālais galvenais elements, kas atrodas saknē. |
| 3. | Min-Heap izmanto augošu prioritāti. | Max-Heap izmanto dilstošo prioritāti. |
| 4. | Min-Heap konstrukcijā mazākajam elementam ir prioritāte. | Max-Heap konstrukcijā lielākajam elementam ir prioritāte. |
| 5. | Min-Heap mazākais elements ir pirmais, kas tiek izmests no kaudzes. | Max-Heap lielākais elements ir pirmais, kas tiek izmests no kaudzes. |
Kaudzīšu pielietojumi :
- Kaudzes kārtošana : Heap Sort ir viens no labākajiem izmantotajiem šķirošanas algoritmiem Binārā kaudze uz kārtot masīvu iekšā O(N*log N) laiks.
- Prioritātes rinda : prioritāro rindu var ieviest, izmantojot kaudzi, jo tā atbalsta ievietot () , dzēst() , ekstraktsMax() , samazinātKey() operācijas iekšā O(log N) laiks.
- Dijkstras īsākais ceļš un Prim minimālais aptverošais koks .
Min-Heap un Max-Heap veiktspējas analīze :
- Iegūt maksimālo vai minimālo elementu: O(1)
- Ievietot elementu Max-Heap vai Min-Heap: O(log N)
- Noņemt maksimālo vai minimālo elementu: O(log N)