DIFFERENZA TRA HEAP MINIMO E HEAP MASSIMO

UN Mucchio è uno speciale albero binario completo . Poiché un heap è un albero binario completo, un heap con N nodi ha ceppo n altezza. È utile rimuovere l'elemento con la priorità più alta o più bassa. In genere è rappresentato come un vettore . Esistono due tipi di heap nel fileMin-Heap

In un Min-Heap la chiave presente nel nodo radice deve essere inferiore o uguale tra le chiavi presenti in tutti i suoi figli. La stessa proprietà deve essere vera ricorsivamente per tutti i sottoalberi di quell'albero binario. In un Min-Heap l'elemento chiave minimo presente alla radice. Di seguito è riportato l'albero binario che soddisfa tutte le proprietà di Min Heap.

int a char

Mucchio massimo

In un Max-Heap la chiave presente nel nodo radice deve essere maggiore o uguale tra le chiavi presenti in tutti i suoi figli. La stessa proprietà deve essere ricorsivamente VERO per tutti i sottoalberi di quell'albero binario. In un Max-Heap l'elemento chiave massimo presente alla radice. Di seguito è riportato l'albero binario che soddisfa tutte le proprietà di Max Heap.

trasforma la stringa in int

	Mucchio minimo	Mucchio massimo
1.	In un Min-Heap la chiave presente nel nodo radice deve essere inferiore o uguale a tra le chiavi presenti in tutti i suoi figli.	In un Max-Heap la chiave presente nel nodo radice deve essere maggiore o uguale tra le chiavi presenti in tutti i suoi figli.
2.	In un Min-Heap l'elemento chiave minimo presente alla radice.	In un Max-Heap l'elemento chiave massimo presente alla radice.
3.	Un Min-Heap utilizza la priorità crescente.	Un Max-Heap utilizza la priorità decrescente.
4.	Nella costruzione di un Min-Heap, l'elemento più piccolo ha la priorità.	Nella costruzione di un Max-Heap, l'elemento più grande ha la priorità.
5.	In un Min-Heap, l'elemento più piccolo è il primo ad essere estratto dall'heap.	In un Max-Heap, l'elemento più grande è il primo ad essere estratto dall'heap.

Applicazioni degli heap :

Ordinamento heap : Heap Sort è uno dei migliori algoritmi di ordinamento che utilizzano Heap binario A ordinare un array In O(N*logN) tempo.
Coda prioritaria : Una coda con priorità può essere implementata utilizzando un heap perché supporta inserire() , eliminare() , estrattoMax() , diminuzioneChiave() operazioni dentro O(logN) tempo.
Il percorso più breve di Dijkstra E Albero di copertura minimo di Prim .

Analisi delle prestazioni di Min-Heap e Max-Heap :

Ottieni elemento massimo o minimo: O(1)
Inserisci elemento in Max-Heap o Min-Heap: O(log N)
Rimuovi elemento massimo o minimo: O(log N)