A Munt és un especial arbre binari complet . Com que un munt és un arbre binari complet, un munt amb N nodes té registre N alçada. És útil eliminar l'element de prioritat més alta o més baixa. Normalment es representa com a matriu . Hi ha dos tipus de Heaps alMin-Heap
En a Min-Heap la clau present al node arrel ha de ser menor o igual entre les claus presents en tots els seus fills. La mateixa propietat ha de ser recursivament certa per a tots els subarbres d'aquest arbre binari. En un Min-Heap l'element clau mínim present a l'arrel. A continuació es mostra l'arbre binari que compleix totes les propietats de Min Heap.
Munt màxim
En a Max-Heap la clau present al node arrel ha de ser major o igual entre les claus presents a tots els seus fills. La mateixa propietat ha de ser recursivament veritat per a tots els subarbres d'aquest arbre binari. En un Max-Heap l'element clau màxim present a l'arrel. A continuació es mostra l'arbre binari que compleix totes les propietats de Max Heap.
Diferència entre Min Heap i Max Heap
| Min Heap | Munt màxim | |
|---|---|---|
| 1. | En un Min-Heap, la clau present al node arrel ha de ser menor o igual que entre les claus presents a tots els seus fills. | En un Max-Heap, la clau present al node arrel ha de ser més gran o igual que entre les claus presents a tots els seus fills. |
| 2. | En un Min-Heap l'element clau mínim present a l'arrel. | En un Max-Heap l'element clau màxim present a l'arrel. |
| 3. | Un Min-Heap utilitza la prioritat ascendent. | Un Max-Heap utilitza la prioritat descendent. |
| 4. | En la construcció d'un Min-Heap, l'element més petit té prioritat. | En la construcció d'un Max-Heap, l'element més gran té prioritat. |
| 5. | En un munt min, l'element més petit és el primer que surt del munt. | En un Max-Heap, l'element més gran és el primer que surt del munt. |
Aplicacions de Heaps :
- Ordenació de pila : Heap Sort és un dels millors algorismes d'ordenació que utilitzen Munt binari a ordenar una matriu en O(N*log N) temps.
- Cua de prioritats : Es pot implementar una cua de prioritat utilitzant un munt perquè és compatible inserir () , suprimir() , extractMax() , disminuirKey() operacions en O (log N) temps.
- El camí més curt de Dijkstra i Arbre d'abast mínim de Prim .
Anàlisi de rendiment de Min-Heap i Max-Heap :
- Obteniu l'element màxim o mínim: O(1)
- Insereix l'element a Max-Heap o Min-Heap: O (log N)
- Elimina l'element màxim o mínim: O(log N)