A Morman este un special arbore binar complet . Întrucât un heap este un arbore binar complet, un heap cu N noduri are jurnalul N înălţime. Este util să eliminați elementul cu cea mai mare sau cea mai mică prioritate. Este de obicei reprezentat ca un matrice . Există două tipuri de grămezi înMin-Heap
Într-o Min-Heap cheia prezentă la nodul rădăcină trebuie să fie mai mică sau egală între cheile prezente la toți copiii săi. Aceeași proprietate trebuie să fie adevărată recursiv pentru toți sub-arborele din acel Arbore Binar. Într-un Min-Heap elementul cheie minim prezent la rădăcină. Mai jos este Arborele Binar care satisface toate proprietățile Min Heap.
Max Heap
Într-o Max-Heap cheia prezentă la nodul rădăcină trebuie să fie mai mare sau egală între cheile prezente la toți copiii săi. Aceeași proprietate trebuie să fie recursiv Adevărat pentru toți sub-arborele din acel Arbore Binar. Într-un Max-Heap, elementul cheie maxim prezent la rădăcină. Mai jos este arborele binar care satisface toate proprietățile lui Max Heap.
Diferența dintre Min Heap și Max Heap
| Min Heap | Max Heap | |
|---|---|---|
| 1. | Într-un Min-Heap, cheia prezentă la nodul rădăcină trebuie să fie mai mică sau egală cu cheile prezente la toți copiii săi. | Într-un Max-Heap, cheia prezentă la nodul rădăcină trebuie să fie mai mare sau egală cu cheile prezente la toți copiii săi. |
| 2. | Într-un Min-Heap elementul cheie minim prezent la rădăcină. | Într-un Max-Heap, elementul cheie maxim prezent la rădăcină. |
| 3. | Un Min-Heap folosește prioritatea ascendentă. | Un Max-Heap folosește prioritatea descendentă. |
| 4. | În construcția unui Min-Heap, cel mai mic element are prioritate. | În construcția unui Max-Heap, cel mai mare element are prioritate. |
| 5. | Într-un Min-Heap, cel mai mic element este primul care este scos din grămada. | Într-un Max-Heap, cel mai mare element este primul care este scos din heap. |
Aplicații ale Heaps :
- Sortare grămadă : Heap Sort este unul dintre cei mai buni algoritmi de sortare care folosesc Heap binar la sortați o matrice în O(N*log N) timp.
- Coada prioritară : O coadă de prioritate poate fi implementată utilizând un heap deoarece acceptă introduce() , șterge() , extractMax() , reduceKey() operațiuni în O(log N) timp.
- Cea mai scurtă cale a lui Dijkstra și Arborele de întindere minim al lui Prim .
Analiza performanței Min-Heap și Max-Heap :
- Obțineți elementul maxim sau minim: O(1)
- Inserați element în Max-Heap sau Min-Heap: O(log N)
- Eliminați elementul maxim sau minim: O(log N)