what is heap data structure java
Questo tutorial spiega cos'è la struttura dei dati di Java Heap e concetti correlati come Min Heap, Max Heap, Heap Sort, Stack vs Heap con esempi:
Un heap è una struttura dati speciale in Java. Un heap è una struttura dati basata su albero e può essere classificato come un albero binario completo. Tutti i nodi dell'heap sono disposti in un ordine specifico.
=> Visita qui per vedere la serie di formazione Java per tutti
Cosa imparerai:
- Struttura dati heap in Java
- Stack vs mucchio in Java
- Conclusione
Struttura dati heap in Java
Nella struttura dei dati dell'heap, il nodo radice viene confrontato con i suoi figli e disposto in base all'ordine. Quindi se a è un nodo radice eb è suo figlio, allora la proprietà, chiave (a)> = chiave (b) genererà un heap massimo.
La relazione sopra tra la radice e il nodo figlio è chiamata 'Proprietà Heap'.
A seconda dell'ordine dei nodi padre-figlio, l'heap è generalmente di due tipi:
# 1) Max-Heap :In un Max-Heap la chiave del nodo radice è la più grande di tutte le chiavi nell'heap. È necessario assicurarsi che la stessa proprietà sia vera per tutti i sottoalberi nell'heap in modo ricorsivo.
Il diagramma seguente mostra un esempio massimo di heap. Notare che il nodo radice è maggiore dei suoi figli.
# 2) Min-Heap :Nel caso di un min-heap, la chiave del nodo radice è la più piccola o minima tra tutte le altre chiavi presenti nell'heap. Come in Max heap, questa proprietà dovrebbe essere ricorsivamente vera in tutti gli altri sottoalberi nell'heap.
Un esempio, di un albero Min-heap, è mostrato di seguito. Come possiamo vedere, la chiave radice è la più piccola di tutte le altre chiavi nell'heap.
Una struttura dati heap può essere utilizzata nelle seguenti aree:
- Gli heap vengono utilizzati principalmente per implementare le code prioritarie.
- Soprattutto min-heap può essere utilizzato per determinare i percorsi più brevi tra i vertici in un grafico.
Come già accennato, la struttura dei dati dell'heap è un albero binario completo che soddisfa la proprietà dell'heap per root e i figli. Questo heap è anche chiamato come file heap binario .
Heap binario
Un heap binario soddisfa le proprietà seguenti:
- Un heap binario è un albero binario completo. In un albero binario completo, tutti i livelli tranne l'ultimo sono completamente riempiti. All'ultimo livello, le chiavi sono il più a sinistra possibile.
- Soddisfa la proprietà heap. L'heap binario può essere max o min-heap a seconda della proprietà dell'heap che soddisfa.
Un heap binario è normalmente rappresentato come un array. Poiché è un albero binario completo, può essere facilmente rappresentato come un array. Pertanto, in una rappresentazione di matrice di heap binario, l'elemento radice sarà A (0) dove A è l'array utilizzato per rappresentare l'heap binario.
Quindi in generale per qualsiasi ithnodo nella rappresentazione dell'array heap binario, A (i), possiamo rappresentare gli indici di altri nodi come mostrato di seguito.
| A ((i-1) / 2) | Rappresenta il nodo padre |
|---|---|
| L'accesso è più veloce. | Più lento dello stack. |
| A ((2 * i) +1) | Rappresenta il nodo figlio sinistro |
| A ((2 * i) +2) | Rappresenta il nodo figlio destro |
Considera il seguente heap binario:
La rappresentazione dell'array dell'heap binario min sopra è la seguente:
Come mostrato sopra, l'heap viene attraversato come per ordine dei livelli cioè gli elementi sono attraversati da sinistra a destra ad ogni livello. Quando gli elementi a un livello sono esauriti, si passa al livello successivo.
Successivamente, implementeremo l'heap binario in Java.
Il programma seguente mostra l'heap binario in Java.
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Produzione:
nHeap = 7 4 6 1 3 2 5
Heap minimo in Java
Un min-heap in Java è un albero binario completo. In min-heap, il nodo radice è più piccolo di tutti gli altri nodi nell'heap. In generale, il valore della chiave di ogni nodo interno è minore o uguale ai suoi nodi figlio.
Per quanto riguarda la rappresentazione dell'array di min-heap, se un nodo è memorizzato nella posizione 'i', il suo nodo figlio sinistro viene memorizzato nella posizione 2i + 1 e quindi il nodo figlio destro è nella posizione 2i + 2. La posizione (i-1) / 2 restituisce il suo nodo padre.
Di seguito sono elencate le varie operazioni supportate da min-heap.
# 1) Inserisci (): Inizialmente, una nuova chiave viene aggiunta alla fine dell'albero. Se la chiave è più grande del suo nodo padre, la proprietà heap viene mantenuta. Altrimenti, dobbiamo attraversare la chiave verso l'alto per soddisfare la proprietà heap. L'operazione di inserimento in heap min richiede tempo O (log n).
# 2) extractMin (): Questa operazione rimuove l'elemento minimo dall'heap. Notare che la proprietà heap deve essere mantenuta dopo aver rimosso l'elemento radice (elemento min) dall'heap. L'intera operazione richiede O (Logn).
# 3) getMin (): getMin () restituisce la radice dell'heap che è anche l'elemento minimo. Questa operazione viene eseguita in tempo O (1).
Di seguito è riportato un esempio di albero per un min-heap.
Il diagramma sopra mostra un albero min-heap. Vediamo che la radice dell'albero è l'elemento minimo dell'albero. Poiché la radice è nella posizione 0, il suo figlio sinistro è posto in 2 * 0 + 1 = 1 e il figlio destro è in 2 * 0 + 2 = 2.
Algoritmo Heap minimo
Di seguito è riportato l'algoritmo per la creazione di un min-heap.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Implementazione dell'heap minimo in Java
Possiamo implementare il min-heap usando array o code di priorità. L'implementazione di min-heap utilizzando le code di priorità è l'implementazione predefinita poiché una coda di priorità viene implementata come min-heap.
Il seguente programma Java implementa il min-heap utilizzando Arrays. Qui usiamo la rappresentazione dell'array per l'heap e quindi applichiamo la funzione heapify per mantenere la proprietà dell'heap di ogni elemento aggiunto all'heap. Infine, visualizziamo l'heap.
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } Produzione:
Max Heap in Java
Un heap max è anche un albero binario completo. In un heap max, il nodo radice è maggiore o uguale ai nodi figlio. In generale, il valore di qualsiasi nodo interno in un heap max è maggiore o uguale ai suoi nodi figlio.
Mentre max heap è mappato su un array, se un nodo è memorizzato nella posizione 'i', il suo figlio sinistro viene memorizzato in 2i +1 e il figlio destro viene memorizzato in 2i + 2.
Il tipico Max-heap apparirà come mostrato di seguito:
Nel diagramma sopra, vediamo che il nodo radice è il più grande nell'heap e i suoi nodi figlio hanno valori inferiori al nodo radice.
Simile a min-heap, anche il max heap può essere rappresentato come un array.
Quindi, se A è un array che rappresenta Max heap, A (0) è il nodo radice. Allo stesso modo, se A (i) è un nodo qualsiasi nell'heap max, i seguenti sono gli altri nodi adiacenti che possono essere rappresentati utilizzando un array.
- A ((i-1) / 2) rappresenta il nodo genitore di A (i).
- A ((2i +1)) rappresenta il nodo figlio sinistro di A (i).
- A (2i + 2) restituisce il nodo figlio destro di A (i).
Di seguito vengono fornite le operazioni eseguibili su Max Heap.
# 1) Inserisci: L'operazione di inserimento inserisce un nuovo valore nell'albero dell'heap max. Viene inserito alla fine dell'albero. Se la nuova chiave (valore) è più piccola del suo nodo padre, la proprietà heap viene mantenuta. In caso contrario, l'albero deve essere heapificato per mantenere la proprietà heap.
differenza tra albero b e albero b +
La complessità temporale dell'operazione di inserimento è O (log n).
# 2) ExtractMax: L'operazione ExtractMax rimuove l'elemento massimo (root) dall'heap max. L'operazione esegue anche l'heap dell'heap massimo per mantenere la proprietà dell'heap. La complessità temporale di questa operazione è O (log n).
# 3) getMax: L'operazione getMax restituisce il nodo radice dell'heap max con la complessità temporale di O (1).
Il seguente programma Java implementa l'heap max. Facciamo uso di ArrayList qui per rappresentare il numero massimo di elementi di heap.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } Produzione:
Heap minimo coda prioritaria in Java
La struttura dei dati della coda di priorità in Java può essere utilizzata direttamente per rappresentare il min-heap. Per impostazione predefinita, la coda di priorità implementa min-heap.
Il programma seguente mostra il min-heap in Java utilizzando Priority Queue.
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Produzione:
Heap massimo coda prioritaria in Java
Per rappresentare l'heap massimo in Java utilizzando la coda Priority, dobbiamo utilizzare Collections.reverseOrder per invertire l'heap minimo. La coda di priorità rappresenta direttamente un min-heap in Java.
Abbiamo implementato Max Heap utilizzando una coda Priority nel programma seguente.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Produzione:
Ordinamento heap in Java
L'ordinamento dell'heap è una tecnica di ordinamento per confronto simile all'ordinamento per selezione in cui selezioniamo un elemento massimo nell'array per ogni iterazione. L'ordinamento dell'heap utilizza la struttura dei dati dell'heap e ordina gli elementi creando l'heap minimo o massimo dagli elementi dell'array da ordinare.
Abbiamo già discusso che in min e max heap, il nodo radice contiene rispettivamente l'elemento minimo e massimo dell'array. Nell'ordinamento dell'heap, l'elemento radice dell'heap (minimo o massimo) viene rimosso e spostato nell'array ordinato. L'heap rimanente viene quindi heapificato per mantenere la proprietà dell'heap.
Quindi dobbiamo eseguire due passaggi in modo ricorsivo per ordinare l'array dato usando l'ordinamento dell'heap.
- Crea un heap dall'array dato.
- Rimuovere ripetutamente l'elemento radice dall'heap e spostarlo nell'array ordinato. Heapify l'heap rimanente.
La complessità temporale dell'ordinamento heap è O (n log n) in tutti i casi. La complessità dello spazio è O (1).
Algoritmo di ordinamento dell'heap in Java
Di seguito sono riportati gli algoritmi di ordinamento dell'heap per ordinare l'array dato in ordine crescente e decrescente.
# 1) Algoritmo di ordinamento heap per ordinare in ordine crescente:
- Crea un heap massimo per ordinare l'array dato.
- Elimina la radice (valore massimo nell'array di input) e spostalo nell'array ordinato. Posiziona l'ultimo elemento dell'array alla radice.
- Heapify la nuova radice dell'heap.
- Ripetere i passaggi 1 e 2 fino a quando l'intero array è ordinato.
# 2) Algoritmo di ordinamento heap per ordinare in ordine decrescente:
- Costruisci un heap minimo per l'array dato.
- Rimuovere la radice (valore minimo nell'array) e scambiarla con l'ultimo elemento nell'array.
- Heapify la nuova radice dell'heap.
- Ripetere i passaggi 1 e 2 fino a quando l'intero array è ordinato.
Implementazione dell'ordinamento dell'heap in Java
Il seguente programma Java utilizza l'ordinamento dell'heap per ordinare un array in ordine crescente. Per questo, costruiamo prima un heap max e quindi scambiamo e heapify ricorsivamente l'elemento root come specificato nell'algoritmo precedente.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } Produzione:
La complessità temporale complessiva della tecnica di ordinamento dell'heap è O (nlogn). La complessità temporale della tecnica heapify è O (logn). Mentre la complessità temporale della creazione dell'heap è O (n).
Stack vs mucchio in Java
Vediamo ora tabularizzare alcune delle differenze tra una struttura dati Stack e un heap.
Pila Mucchio Uno stack è una struttura dati lineare. Un heap è una struttura dati gerarchica. Segue l'ordine LIFO (Last In, First Out). L'attraversamento è in ordine di livello. Utilizzato principalmente per l'allocazione della memoria statica. Utilizzato per l'allocazione dinamica della memoria. La memoria viene allocata in modo contiguo. La memoria viene allocata in posizioni casuali. La dimensione dello stack è limitata in base al sistema operativo. Nessun limite alla dimensione dell'heap imposto dal sistema operativo. Stack ha accesso solo alle variabili locali. Heap ha variabili globali assegnate ad esso. L'allocazione / deallocazione della memoria è automatica. L'assegnazione / deallocazione deve essere eseguita manualmente dal programmatore. Lo stack può essere implementato utilizzando Arrays, Linked List, ArrayList, ecc. O qualsiasi altra struttura di dati lineari. L'heap viene implementato utilizzando array o alberi. Costo di manutenzione se inferiore. Più costoso da mantenere. Può provocare una carenza di memoria poiché la memoria è limitata. Non manca la memoria ma può soffrire di frammentazione della memoria.
Domande frequenti
D # 1) Lo stack è più veloce di Heap?
Risposta: Uno stack è più veloce dell'heap poiché l'accesso è lineare nello stack rispetto all'heap.
D # 2) A cosa serve un heap?
Risposta: L'heap viene utilizzato principalmente negli algoritmi che trovano il percorso minimo o più breve tra due punti come l'algoritmo di Dijkstra, per l'ordinamento utilizzando l'ordinamento dell'heap, per le implementazioni della coda prioritaria (min-heap), ecc.
D # 3) Cos'è un mucchio? Quali sono i suoi tipi?
Risposta: Un heap è una struttura di dati gerarchica basata su albero. Un mucchio è un albero binario completo. Gli heap sono di due tipi, ovvero Max heap in cui il nodo radice è il più grande tra tutti i nodi; Heap minimo in cui il nodo radice è il più piccolo o il minimo tra tutte le chiavi.
D # 4) Quali sono i vantaggi di Heap rispetto a uno stack?
Risposta: Il vantaggio principale dell'heap rispetto allo stack è nell'heap, la memoria viene allocata dinamicamente e quindi non c'è limite alla quantità di memoria che può essere utilizzata. In secondo luogo, solo le variabili locali possono essere allocate nello stack mentre possiamo anche allocare variabili globali nell'heap.
D # 5) Heap può avere duplicati?
Risposta: Sì, non ci sono restrizioni sull'avere nodi con chiavi duplicate nell'heap poiché l'heap è un albero binario completo e non soddisfa le proprietà dell'albero di ricerca binario.
Conclusione
In questo tutorial, abbiamo discusso i tipi di heap e di ordinamento di heap utilizzando i tipi di heap. Abbiamo anche visto l'implementazione dettagliata dei suoi tipi in Java.
=> Dai un'occhiata alla guida di formazione Java perfetta qui.
Lettura consigliata
- Tutorial Java Graph - Come implementare la struttura dati del grafico
- Introduzione alle strutture dati in C ++
- Ordinamento heap in C ++ con esempi
- Struttura dei dati ad albero e heap AVL in C ++
- Struttura dei dati dell'albero binario in C ++
- Struttura dei dati della coda in C ++ con illustrazione
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Nozioni di base su Java: sintassi Java, classe Java e concetti principali di Java
