A Kup je posebnež popolno binarno drevo . Ker je kopica popolno binarno drevo, kopica z n vozlišča ima dnevnik N višina. Koristno je odstraniti element z najvišjo ali najnižjo prioriteto. Običajno je predstavljen kot niz . Obstajata dve vrsti kupov vMin-kup
V Min-kup ključ, ki je prisoten v korenskem vozlišču, mora biti manjši ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih elementih. Ista lastnost mora biti rekurzivno resnična za vsa poddrevesa v tem binarnem drevesu. V Min-Heap minimalni ključni element, ki je prisoten v korenu. Spodaj je binarno drevo, ki izpolnjuje vse lastnosti Min Heap.
Max Heap
V Max-Heap ključ, ki je prisoten v korenskem vozlišču, mora biti večji ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih. Enaka lastnost mora biti rekurzivno prav za vsa poddrevesa v tem binarnem drevesu. V Max-Heap največji ključni element, ki je prisoten v korenu. Spodaj je binarno drevo, ki izpolnjuje vse lastnosti Max Heapa.
Razlika med Min Heap in Max Heap
| Najmanjša kopica | Max Heap | |
|---|---|---|
| 1. | V Min-Heap mora biti ključ, ki je prisoten v korenskem vozlišču, manjši ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih elementih. | V Max-Heap mora biti ključ, ki je prisoten v korenskem vozlišču, večji ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih. |
| 2. | V Min-Heap minimalni ključni element, ki je prisoten v korenu. | V Max-Heap največji ključni element, ki je prisoten v korenu. |
| 3. | Min-Heap uporablja naraščajočo prioriteto. | Max-Heap uporablja padajočo prioriteto. |
| 4. | Pri konstrukciji Min-Heap ima prednost najmanjši element. | Pri konstrukciji Max-Heap ima prednost največji element. |
| 5. | V Min-Heap-u je najmanjši element prvi, ki se odstrani iz kupa. | V največji kopici je največji element prvi, ki se odstrani iz kopice. |
Aplikacije Heaps :
- Razvrščanje kopice : Heap Sort je eden najboljših algoritmov za razvrščanje, ki uporabljajo Binarna kopica do razvrsti niz v O(N*log N) čas.
- Prednostna čakalna vrsta : Prednostno čakalno vrsto je mogoče implementirati z uporabo kopice, ker podpira vstavi() , izbrisati() , izvlečekMax() , zmanjšajKey() operacije v O(log N) čas.
- Dijkstrova najkrajša pot in Primovo minimalno vpeto drevo .
Analiza zmogljivosti Min-Heap in Max-Heap :
- Pridobite največji ali najmanjši element: O(1)
- Vstavi element v Max-Heap ali Min-Heap: O(log N)
- Odstrani največji ali najmanjši element: O(log N)