Questo articolo ti fornirà una panoramica completa del funzionamento dell'ordinamento heap e successivamente impareremo a implementare un heap binario in Java.
Ecco l'ordine del giorno per questo articolo:
Cominciamo!
Cos'è l'ordinamento di heap?
Heap è fondamentalmente una struttura dati basata su albero. Ha nodi. Il nodo comprende alcuni elementi. Ogni nodo contiene un elemento.
I nodi possono avere figli. Se nel caso non ci siano bambini, si chiama Foglia.
Ci sono due regole da seguire:
- Il valore di ogni nodo deve essere minore o uguale a tutti i valori memorizzati nei suoi figli.
- Ha la minore altezza possibile.
Gli heap sono estremamente efficienti nell'estrazione del fileelemento minimo o massimo.
Passiamo ora al min heap!
Min Heap
L'heap minimo è un albero binario completo in cui il valore dell'elemento radice è minore o uguale a uno degli elementi figlio.
Rappresentazione di min heap
Arr [(i-1) / 2]: questo restituirà il nodo genitore.
come creare un array di oggetti in java
Arr [(2 * i) + 1]: questo restituirà il nodo figlio sinistro.
Arr [(2 * i) + 2]: questo restituirà il nodo figlio destro.
Esistono alcuni metodi di Min Heap:
- inserire(): Viene aggiunta una nuova chiave alla fine dell'albero. Nel caso in cui la nuova chiave sia più grande del genitore, non è necessario fare nulla, altrimenti dobbiamo attraversare per impostare la proprietà heap.
- getMin (): questo metodo aiuta a restituire l'elemento radice.
- extractMin (): questo metodo restituisce il minimoelemento.
Passiamo ora a Max heap.
Max heap
L'heap massimo è un albero binario completo in cui il valore dell'elemento radice è maggiore o uguale a uno degli elementi figlio.
Max heap comprende anche diversi metodi!
- Inserisci (): inserirà un elemento nell'heap.
- Elimina() : cancellerà un elemento dall'heap.
- FindMax (): troverà l'elemento massimo dall'heap.
- printHeap (): Stamperà il contenuto dell'heap
Ora lascia che ti mostri l'implementazione dell'heap attraverso un diagramma e successivamente un Javacodice.
Implementazione dell'heap in Java
Diagramma:
Il diagramma sopra mostra l'heap binario in Java. Come hai appreso che ci sono due heap: Min heap e Max heap, ecco un diagramma:
passare per valore in java
Ora, passando al nostro prossimo segmento, vedremo come implementare un heap binario in Java.
Codice:
public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Questo inizializzerà il nostro heap con la dimensione predefinita. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Questo controllerà se l'heap è vuoto o meno * Complessità: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Questo controllerà se l'heap è pieno o meno * Complessità: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Questo inserirà un nuovo elemento nell'heap * Complessità: O (log N) * Come scenario peggiore, dobbiamo attraversare fino alla radice * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert nuovo elemento ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Questo cancellerà l'elemento all'indice x * Complessità: O (log N) * * / public int delete (int x) {if (isEmpty ()) lancia una nuova NoSuchElementException ('Heap è vuoto, nessun elemento da eliminare') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Questo metodo utilizzato per mantenere la proprietà heap durante l'inserimento di un elemento. * * / 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} / ** * Questo metodo è utilizzato per mantenere la proprietà heap durante l'eliminazione di un elemento. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Questo metodo utilizzato per stampare tutti gli elementi dell'heap * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 iCon questo, arriviamo alla fine di questo articolo su Binary Heap in Java. Controlla il da Edureka, una società di formazione online affidabile con una rete di oltre 250.000 studenti soddisfatti sparsi in tutto il mondo. Il corso di formazione e certificazione Java J2EE e SOA di Edureka è progettato per studenti e professionisti che desiderano diventare sviluppatori Java. Il corso è progettato per darti un vantaggio nella programmazione Java e formarti per concetti Java sia di base che avanzati insieme a vari framework Java come Hibernate e Spring.
Hai domande per noi? Per favore, menzionalo nella sezione commenti di questo blog 'Java ArrayList' e ti risponderemo il prima possibile.