UN Min-Heap è definito come un tipo di La struttura dati heap è un tipo di albero binario comunemente utilizzato in informatica per vari scopi, tra cui l'ordinamento, la ricerca e l'organizzazione dei dati.
Introduzione a Min-Heap: tutorial sulla struttura dei dati e sugli algoritmi
Scopo e casi d'uso di Min-Heap:
- Implementazione della coda prioritaria: Uno degli usi principali della struttura dei dati heap è l'implementazione delle code con priorità.
- Algoritmo di Dijkstra : L’algoritmo di Dijkstra è un algoritmo del percorso minimo che trova il percorso più breve tra due nodi in un grafico. È possibile utilizzare un heap minimo per tenere traccia dei nodi non visitati con la distanza più piccola dal nodo di origine.
- Ordinamento: Un heap minimo può essere utilizzato come algoritmo di ordinamento per ordinare in modo efficiente una raccolta di elementi in ordine crescente.
- Risultato mediano: Un heap minimo può essere utilizzato per trovare in modo efficiente la mediana di un flusso di numeri. Possiamo usare un heap minimo per memorizzare la metà più grande dei numeri e un heap massimo per memorizzare la metà più piccola. La mediana sarà la radice dell'heap minimo.
Struttura dei dati Min-Heap in diverse lingue:
1. Heap minimo in C++
Un heap minimo può essere implementato utilizzando il metodo priorità_coda contenitore dalla libreria di modelli standard (STL). IL priorità_coda container è un tipo di adattatore container che fornisce un modo per archiviare elementi in una struttura dati simile a una coda in cui a ciascun elemento è associata una priorità.
Sintassi :
C++
priority_queue < int, vector , maggiore >Hmin;>
2. Min-Heap in Java
In Java, è possibile implementare un heap minimo utilizzando il metodo PriorityQueue classe da pacchetto java.util . La classe PriorityQueue è una coda di priorità che fornisce un modo per archiviare elementi in una struttura dati simile a una coda in cui a ciascun elemento è associata una priorità.
Sintassi :
Giava PriorityQueue minHeap = nuova PriorityQueue ();>
3. Heap minimo in Python
In Python, un heap minimo può essere implementato utilizzando il metodo heapq modulo, che fornisce funzioni per l'implementazione degli heap. Nello specifico, il heapq Il modulo fornisce un modo per creare e manipolare strutture di dati heap.
Sintassi:
Pitone heap = [] heapify(heap)>
4. Heap minimo in C#
In C# è possibile implementare un heap minimo utilizzando la classe PriorityQueue da Spazio dei nomi System.Collections.Generic . La classe PriorityQueue è una coda di priorità che fornisce un modo per archiviare elementi in una struttura dati simile a una coda in cui a ciascun elemento è associata una priorità.
Sintassi:
C# var minHeap = new PriorityQueue ();>
5. Heap minimo in JavaScript
Un heap minimo è un albero binario in cui ogni nodo ha un valore inferiore o uguale ai suoi figli. In JavaScript, puoi implementare un heap minimo utilizzando un array, dove il primo elemento rappresenta il nodo radice e i figli di un nodo all'indice io si trovano negli indici 2i+1 E 2i+2.
Sintassi:
JavaScript const minHeap = new MinHeap();>
Differenza tra Heap minimo e Heap massimo:
|
materiale angolare | 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. |
Implementazione interna della struttura dei dati Min-Heap:
UN L'heap minimo è in genere rappresentato come un array .
- L'elemento radice sarà a Arrivo[0] .
- Per ogni i-esimo nodo Arr[i] :
- Arr[(i -1) / 2] restituisce il suo nodo genitore.
- Arr[(2 * i) + 1] restituisce il nodo figlio sinistro.
- Arr[(2 * i) + 2] restituisce il nodo figlio destro.
L'implementazione interna del Min-Heap richiede 3 passaggi principali:
- Inserimento : Per inserire un elemento nell'heap minimo, prima aggiungiamo l'elemento alla fine dell'array e quindi regoliamo la proprietà dell'heap scambiando ripetutamente l'elemento con il suo genitore finché non si trova nella posizione corretta.
- Cancellazione : Per rimuovere l'elemento minimo dall'heap minimo, scambiamo prima il nodo radice con l'ultimo elemento dell'array, rimuoviamo l'ultimo elemento e quindi regoliamo la proprietà dell'heap scambiando ripetutamente l'elemento con il suo figlio più piccolo finché non si trova nell'heap minimo posizione corretta.
- Heapify : è possibile utilizzare un'operazione di heapify per creare un heap minimo da un array non ordinato.
Operazioni sulla struttura dati Min-heap e loro implementazione:
Ecco alcune operazioni comuni che possono essere eseguite su una struttura dati heap,
1. Inserimento nella struttura dati Min-Heap :
Gli elementi possono essere inseriti nell'heap seguendo un approccio simile a quello discusso sopra per l'eliminazione. L'idea è:
- L’operazione di inserimento in un min-heap prevede i seguenti passaggi:
- Aggiungi il nuovo elemento alla fine dell'heap, nella successiva posizione disponibile nell'ultimo livello dell'albero.
- Confronta il nuovo elemento con il suo genitore. Se il genitore è maggiore del nuovo elemento, scambiali.
- Ripetere il passaggio 2 finché il genitore non è più piccolo o uguale al nuovo elemento o finché il nuovo elemento non raggiunge la radice dell'albero.
- Il nuovo elemento è ora nella posizione corretta nell'heap minimo e la proprietà dell'heap è soddisfatta.
Illustrazione:
Supponiamo che l'Heap sia un Min-Heap come:
Inserimento nel Min-Heap
Implementazione dell'operazione di inserimento in Min-Heap:
C++ #include #include using namespace std; // Function to insert a new element into the min-heap void insert_min_heap(vector & heap, int value) { // Aggiunge il nuovo elemento alla fine dell'heap heap.push_back(value); // Ottiene l'indice dell'ultimo elemento int indice = heap.size() - 1; // Confronta il nuovo elemento con il suo genitore e scambialo se // necessario while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]); // Sposta l'albero verso l'alto fino al genitore dell'elemento // corrente indice = (indice - 1) / 2; } } // Funzione principale per testare la funzione insert_min_heap int main() { vettore mucchio; valori int[] = { 10, 7, 11, 5, 4, 13 }; int n = dimensionedi(valori) / dimensionedi(valori[0]); for (int i = 0; i< n; i++) { insert_min_heap(heap, values[i]); cout << 'Inserted ' << values[i] << ' into the min-heap: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; } return 0; }>
Giava import java.util.*; public class GFG { // Function to insert a new element into the min-heap public static void insertMinHeap(int[] heap, int size, int value) { // Add the new element to the end of the heap heap[size] = value; // Get the index of the last element int index = size; // Compare the new element with its parent and swap // if necessary while (index>0 && heap[(indice - 1) / 2]> heap[indice]) { swap(heap, indice, (indice - 1) / 2); // Sposta l'albero verso l'alto fino al genitore dell'elemento // corrente indice = (indice - 1) / 2; } } // Funzione per scambiare due elementi in un array public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temperatura; } // Funzione principale per testare la funzione insertMinHeap public static void main(String[] args) { int[] heap = new int[6]; int[] valori = { 10, 7, 11, 5, 4, 13 }; dimensione intera = 0; for (int i = 0; i< values.length; i++) { insertMinHeap(heap, size, values[i]); size++; System.out.print('Inserted ' + values[i] + ' into the min-heap: '); for (int j = 0; j < size; j++) { System.out.print(heap[j] + ' '); } System.out.println(); } } }> Python3 def insert_min_heap(heap, value): # Add the new element to the end of the heap heap.append(value) # Get the index of the last element index = len(heap) - 1 # Compare the new element with its parent and swap if necessary while index>0 e heap[(indice - 1) // 2]> heap[indice]: heap[indice], heap[(indice - 1) // 2] = heap[(indice - 1) // 2], heap[ indice] # Sposta l'albero al genitore dell'elemento corrente indice = (indice - 1) // 2 heap = [] valori = [10, 7, 11, 5, 4, 13] for valore in valori: insert_min_heap( heap, valore) print(f'Inserito {valore} nell'heap minimo: {heap}')> C# using System; using System.Collections.Generic; public class Program { // Function to insert a new element into the min-heap static void InsertMinHeap(List heap, int value) { // Aggiunge il nuovo elemento alla fine dell'heap heap.Add(value); // Ottieni l'indice dell'ultimo elemento int indice = heap.Count - 1; // Confronta il nuovo elemento con il suo genitore e scambia // se necessario while (index> 0 && heap[(index - 1) / 2]> heap[index]) { int temp = heap[index]; heap[indice] = heap[(indice - 1) / 2]; heap[(indice - 1) / 2] = temperatura; // Sposta l'albero verso l'alto fino al genitore dell'elemento // corrente indice = (indice - 1) / 2; } } // Funzione principale per testare la funzione InsertMinHeap public static void Main() { List heap = nuova lista (); int[] valori = { 10, 7, 11, 5, 4, 13 }; foreach(int valore in valori) { InsertMinHeap(heap, valore); Console.Write('Inserito ' + valore + ' nell'heap minimo: '); foreach(int elemento nell'heap) { Console.Write(elemento + ' '); } Console.WriteLine(); } } }> Javascript function insertMinHeap(heap, value) { heap.push(value); let index = heap.length - 1; let parentIndex = Math.floor((index - 1) / 2); while (index>0 && heap[parentIndex]> heap[index]) { [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]]; indice = indicegenitore; parentIndex = Math.floor((indice - 1) / 2); } } // Esempio di utilizzo const heap = []; valori const = [10, 7, 11, 5, 4, 13]; for (valore costante dei valori) { insertMinHeap(heap, valore); console.log(`Inserito ${value} nell'heap minimo: ${heap}`); }> Produzione
Inserted 10 into the min-heap: 10 Inserted 7 into the min-heap: 7 10 Inserted 11 into the min-heap: 7 10 11 Inserted 5 into the min-heap: 5 7 11 10 Inserted 4 into the min-heap: 4 5 11 10 7 Inser...>
Complessità temporale: O(log(n)) ( dove n è il numero di elementi nell'heap )
Spazio ausiliario: SU)
2. Cancellazione nella struttura dei dati Min-Heap :
Rimozione dell'elemento più piccolo (la radice) dall'heap minimo. La radice viene sostituita dall'ultimo elemento nell'heap, quindi la proprietà dell'heap viene ripristinata scambiando la nuova radice con il suo figlio più piccolo finché il genitore non diventa più piccolo di entrambi i figli o finché la nuova radice non raggiunge un nodo foglia.
- Sostituisci la radice o l'elemento da eliminare con l'ultimo elemento.
- Elimina l'ultimo elemento dall'heap.
- Poiché l'ultimo elemento è ora posizionato nella posizione del nodo radice. Pertanto, potrebbe non seguire la proprietà heap. Pertanto, heapifica l'ultimo nodo posizionato nella posizione della radice.
Illustrazione :
Supponiamo che l'Heap sia un Min-Heap come:
Struttura dei dati con heap minimo
L'elemento da eliminare è root, ovvero 13.
Processi :
L'ultimo elemento è 100.
Passo 1: Sostituisci l'ultimo elemento con root ed eliminalo.
Struttura dei dati con heap minimo
Passo 2 : Heapifica la radice.
Heap finale:
java math.randomStruttura dei dati con heap minimo
Implementazione dell'operazione di eliminazione in Min-Heap:
C++ #include #include using namespace std; // Function to insert a new element into the min-heap void insert_min_heap(vector & heap, int value) { // Aggiunge il nuovo elemento alla fine dell'heap heap.push_back(value); // Ottiene l'indice dell'ultimo elemento int indice = heap.size() - 1; // Confronta il nuovo elemento con il suo genitore e scambialo se // necessario while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]); // Sposta l'albero verso l'alto fino al genitore dell'elemento // corrente indice = (indice - 1) / 2; } } // Funzione per eliminare un nodo dal min-heap void delete_min_heap(vettore & heap, int value) { // Trova l'indice dell'elemento da eliminare int indice = -1; for (int i = 0; i< heap.size(); i++) { if (heap[i] == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last // element heap[index] = heap[heap.size() - 1]; // Remove the last element heap.pop_back(); // Heapify the tree starting from the element at the // deleted index while (true) { int left_child = 2 * index + 1; int right_child = 2 * index + 2; int smallest = index; if (left_child < heap.size() && heap[left_child] < heap[smallest]) { smallest = left_child; } if (right_child < heap.size() && heap[right_child] < heap[smallest]) { smallest = right_child; } if (smallest != index) { swap(heap[index], heap[smallest]); index = smallest; } else { break; } } } // Main function to test the insert_min_heap and // delete_min_heap functions int main() { vector mucchio; valori int[] = { 13, 16, 31, 41, 51, 100 }; int n = dimensionedi(valori) / dimensionedi(valori[0]); for (int i = 0; i< n; i++) { insert_min_heap(heap, values[i]); } cout << 'Initial heap: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; delete_min_heap(heap, 13); cout << 'Heap after deleting 13: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; return 0; }>
Giava import java.util.*; public class GFG { // Function to insert a new element into the min-heap public static void insertMinHeap(List heap, int value) { // Aggiunge il nuovo elemento alla fine dell'heap heap.add(value); // Ottiene l'indice dell'ultimo elemento int indice = heap.size() - 1; // Confronta il nuovo elemento con il suo genitore e scambia // se necessario while (index> 0 && heap.get((index - 1) / 2)> heap.get(index)) { Collections.swap(heap, index, (indice - 1) / 2); // Sposta l'albero verso l'alto fino al genitore dell'elemento // corrente indice = (indice - 1) / 2; } } // Funzione per eliminare un nodo dal min-heap pubblico statico void deleteMinHeap(List heap, int value) { // Trova l'indice dell'elemento da eliminare int indice = -1; for (int i = 0; i< heap.size(); i++) { if (heap.get(i) == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last // element heap.set(index, heap.get(heap.size() - 1)); // Remove the last element heap.remove(heap.size() - 1); // Heapify the tree starting from the element at the // deleted index while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int smallest = index; if (leftChild < heap.size() && heap.get(leftChild) < heap.get(smallest)) { smallest = leftChild; } if (rightChild < heap.size() && heap.get(rightChild) < heap.get(smallest)) { smallest = rightChild; } if (smallest != index) { Collections.swap(heap, index, smallest); index = smallest; } else { break; } } } // Main function to test the insertMinHeap and // deleteMinHeap functions public static void main(String[] args) { List heap = nuovo ArrayList (); int[] valori = { 13, 16, 31, 41, 51, 100 }; int n = valori.lunghezza; for (int i = 0; i< n; i++) { insertMinHeap(heap, values[i]); } System.out.print('Initial heap: '); for (int j = 0; j < heap.size(); j++) { System.out.print(heap.get(j) + ' '); } System.out.println(); deleteMinHeap(heap, 13); System.out.print('Heap after deleting 13: '); for (int j = 0; j < heap.size(); j++) { System.out.print(heap.get(j) + ' '); } System.out.println(); } }> Python3 def insert_min_heap(heap, value): heap.append(value) index = len(heap) - 1 while index>0 e heap[(indice - 1) // 2]> heap[indice]: heap[indice], heap[(indice - 1) // 2] = heap[(indice - 1) // 2], heap[ indice] indice = (indice - 1) // 2 def delete_min_heap(heap, valore): indice = -1 for i in range(len(heap)): if heap[i] == valore: indice = i break if indice == -1: return heap[indice] = heap[-1] heap.pop() while True: left_child = 2 * indice + 1 right_child = 2 * indice + 2 più piccolo = indice if left_child< len(heap) and heap[left_child] < heap[smallest]: smallest = left_child if right_child < len(heap) and heap[right_child] < heap[smallest]: smallest = right_child if smallest != index: heap[index], heap[smallest] = heap[smallest], heap[index] index = smallest else: break heap = [] values = [13, 16, 31, 41, 51, 100] for value in values: insert_min_heap(heap, value) print('Initial heap:', heap) delete_min_heap(heap, 13) print('Heap after deleting 13:', heap)> C# using System; using System.Collections.Generic; class MinHeap { private List heap = nuova lista (); public void Insert(int valore) { heap.Add(valore); indice int = heap.Count - 1; while (indice> 0 && heap[(indice - 1) / 2]> heap[indice]) { Swap(indice, (indice - 1) / 2); indice = (indice - 1) / 2; } } public void Elimina(int valore) { int indice = heap.IndexOf(valore); if (indice == -1) { return; } heap[indice] = heap[heap.Conteggio - 1]; heap.RemoveAt(heap.Count - 1); while (true) { int leftChild = 2 * indice + 1; int rightChild = 2 * indice + 2; int più piccolo = indice; se (leftChild< heap.Count && heap[leftChild] < heap[smallest]) { smallest = leftChild; } if (rightChild < heap.Count && heap[rightChild] < heap[smallest]) { smallest = rightChild; } if (smallest != index) { Swap(index, smallest); index = smallest; } else { break; } } } private void Swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } public void Print() { for (int i = 0; i < heap.Count; i++) { Console.Write(heap[i] + ' '); } Console.WriteLine(); } } class Program { static void Main(string[] args) { MinHeap heap = new MinHeap(); int[] values = { 13, 16, 31, 41, 51, 100 }; for (int i = 0; i < values.Length; i++) { heap.Insert(values[i]); } Console.Write('Initial heap: '); heap.Print(); heap.Delete(13); Console.Write('Heap after deleting 13: '); heap.Print(); } }> Javascript function insertMinHeap(heap, value) { // Add the new element to the end of the heap heap.push(value); // Get the index of the last element let index = heap.length - 1; // Compare the new element with its parent and swap if necessary for (let flr = Math.floor((index - 1) / 2); index>0 && heap[flr]> heap[indice]; flr = Math.floor((indice - 1) / 2)) { [heap[indice], heap[flr]] = [ heap[flr], heap[indice],]; // Sposta l'albero verso l'alto fino al genitore dell'elemento corrente indice = Math.floor((indice - 1) / 2); } } function deleteMinHeap(heap, value) { // Trova l'indice dell'elemento da eliminare let index = -1; per (sia i = 0; i< heap.length; i++) { if (heap[i] == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last element heap[index] = heap[heap.length - 1]; // Remove the last element heap.pop(); // Heapify the tree starting from the element at the deleted index while (true) { let left_child = 2 * index + 1; let right_child = 2 * index + 2; let smallest = index; if (left_child < heap.length && heap[left_child] < heap[smallest]) { smallest = left_child; } if (right_child < heap.length && heap[right_child] < heap[smallest]) { smallest = right_child; } if (smallest != index) { [heap[index], heap[smallest]] = [heap[smallest], heap[index]]; index = smallest; } else { break; } } } // Main function to test the insertMinHeap and deleteMinHeap functions let heap = []; let values = [13, 16, 31, 41, 51, 100]; for (let i = 0; i < values.length; i++) { insertMinHeap(heap, values[i]); } console.log('Initial heap: ' + heap.join(' ')); deleteMinHeap(heap, 13); console.log('Heap after deleting 13: ' + heap.join(' '));> Produzione
Initial heap: 13 16 31 41 51 100 Heap after deleting 13: 16 41 31 100 51>
Complessità temporale : O(log n) dove n è il numero di elementi nell'heap
Spazio ausiliario: SU)
3. Operazione Peek sulla struttura dati Min-Heap:
Per accedere all'elemento minimo (ovvero la radice dell'heap), viene restituito il valore del nodo radice. La complessità temporale del peek in un min-heap è O(1).
Struttura dati heap minima
Implementazione dell'operazione Peek in Min-Heap:
C++ #include #include #include using namespace std; int main() { // Create a max heap with some elements using a // priority_queue priority_queue , maggiore >minHeap; minHeap.push(9); minHeap.push(8); minHeap.push(7); minHeap.push(6); minHeap.push(5); minHeap.push(4); minHeap.push(3); minHeap.push(2); minHeap.push(1); // Ottieni l'elemento di picco (ovvero l'elemento più grande) int peakElement = minHeap.top(); // Stampa l'elemento di picco cout<< 'Peak element: ' << peakElement << std::endl; return 0; }> Giava import java.util.PriorityQueue; public class GFG { public static void main(String[] args) { // Create a max heap with some elements using a // PriorityQueue PriorityQueue minHeap = nuova PriorityQueue(); minHeap.add(9); minHeap.add(8); minHeap.add(7); minHeap.add(6); minHeap.add(5); minHeap.add(4); minHeap.add(3); minHeap.add(2); minHeap.add(1); // Ottieni l'elemento di picco (ovvero l'elemento più grande) int peakElement = minHeap.peek(); // Stampa l'elemento picco System.out.println('Elemento picco: ' + peakElement); } }> Python3 import heapq # Create a min heap with some elements using a list min_heap = [9, 8, 7, 6, 5, 4, 3, 2, 1] heapq.heapify(min_heap) # Get the peak element (i.e., the smallest element) peak_element = heapq.nsmallest(1, min_heap)[0] # Print the peak element print('Peak element:', peak_element)> C# using System; using System.Collections.Generic; public class GFG { public static void Main() { // Create a min heap with some elements using a // PriorityQueue var minHeap = new PriorityQueue (); minHeap.Enqueue(9); minHeap.Enqueue(8); minHeap.Enqueue(7); minHeap.Enqueue(6); minHeap.Enqueue(5); minHeap.Enqueue(4); minHeap.Enqueue(3); minHeap.Enqueue(2); minHeap.Enqueue(1); // Ottieni l'elemento di picco (ovvero l'elemento più piccolo) int peakElement = minHeap.Peek(); // Stampa l'elemento di picco Console.WriteLine('Elemento di picco: ' + peakElement); } }> Javascript const PriorityQueue = require('fast-priority-queue'); // Create a min heap with some elements using a PriorityQueue const minHeap = new PriorityQueue((a, b) =>a-b); minHeap.add(9); minHeap.add(8); minHeap.add(7); minHeap.add(6); minHeap.add(5); minHeap.add(4); minHeap.add(3); minHeap.add(2); minHeap.add(1); // Ottieni l'elemento di picco (ovvero l'elemento più piccolo) const peakElement = minHeap.peek(); // Stampa l'elemento di picco console.log(`Elemento di picco: ${peakElement}`);> Produzione
Peak element: 1>
Complessità temporale : In un heap minimo implementato utilizzando un array o una lista, è possibile accedere all'elemento di picco in tempo costante, O(1), poiché si trova sempre alla radice dell'heap.
In un heap minimo implementato utilizzando un albero binario, è possibile accedere all'elemento peak anche in tempo O(1), poiché si trova sempre alla radice dell'albero.
Spazio ausiliario: SU)
4. Operazione Heapify sulla struttura dati Min-Heap:
È possibile utilizzare un'operazione di heapify per creare un heap minimo da un array non ordinato. Questa operazione viene eseguita iniziando dall'ultimo nodo non foglia ed eseguendo ripetutamente l'operazione di bubble down finché tutti i nodi non soddisfano la proprietà heap.
Operazione Heapify in Min Heap
Implementazione dell'operazione Heapify in Min-Heap:
C++ #include #include using namespace std; void minHeapify(vector &arr, int i, int n) { int più piccolo = i; int l = 2*i + 1; intr = 2*i+2; se (l< n && arr[l] < arr[smallest]) smallest = l; if (r < n && arr[r] < arr[smallest]) smallest = r; if (smallest != i) { swap(arr[i], arr[smallest]); minHeapify(arr, smallest, n); } } int main() { vector arr = {10, 5, 15, 2, 20, 30}; cout<< 'Original array: '; for (int i = 0; i < arr.size(); i++) cout << arr[i] << ' '; // Perform heapify operation on min-heap for (int i = arr.size()/2 - 1; i>= 0; i--) minHeapify(arr, i, arr.size()); cout<< '
Min-Heap after heapify operation: '; for (int i = 0; i < arr.size(); i++) cout << arr[i] << ' '; return 0; }>
Giava // Java code of Heapify operation in Min-Heap import java.util.Arrays; import java.util.List; public class Main { // Function to maintain the min-heap property of the heap rooted at index 'i' public static void minHeapify(List arr, int i, int n) { // Supponiamo che la radice sia l'elemento più piccolo inizialmente int più piccolo = i; // Calcola gli indici del figlio sinistro e destro del nodo corrente int l = 2 * i + 1; int r = 2 * i + 2; // Confronta il bambino sinistro con l'attuale più piccolo if (l< n && arr.get(l) < arr.get(smallest)) smallest = l; // Compare the right child with the current smallest if (r < n && arr.get(r) < arr.get(smallest)) smallest = r; // If the current node is not the smallest, swap it with the smallest child if (smallest != i) { int temp = arr.get(i); arr.set(i, arr.get(smallest)); arr.set(smallest, temp); // Recursively heapify the subtree rooted at the smallest child minHeapify(arr, smallest, n); } } public static void main(String[] args) { // Create a list representing the array List arr = Arrays.asList(10, 5, 15, 2, 20, 30); System.out.print('Array originale: '); // Stampa l'array originale per (int i = 0; i< arr.size(); i++) System.out.print(arr.get(i) + ' '); // Perform heapify operation on the min-heap // Start from the last non-leaf node and go up to the root of the tree for (int i = arr.size() / 2 - 1; i>= 0; i--) minHeapify(arr, i, arr.size()); System.out.print('
Min-Heap dopo l'operazione heapify: '); // Stampa l'heap minimo dopo l'operazione di heapify per (int i = 0; i< arr.size(); i++) System.out.print(arr.get(i) + ' '); } }> Pitone def minHeapify(arr, i, n): smallest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] < arr[smallest]: smallest = left if right < n and arr[right] < arr[smallest]: smallest = right if smallest != i: arr[i], arr[smallest] = arr[smallest], arr[i] minHeapify(arr, smallest, n) if __name__ == '__main__': arr = [10, 5, 15, 2, 20, 30] print('Original array:', arr) # Perform heapify operation on a min-heap for i in range(len(arr) // 2 - 1, -1, -1): minHeapify(arr, i, len(arr)) print('Min-Heap after heapify operation:', arr)> C# using System; using System.Collections.Generic; class GFG { // Function to perform the minHeapify operation on a min-heap. static void MinHeapify(List arr, int i, int n) { int più piccolo = i; int sinistro = 2 * i + 1; int destra = 2 * i + 2; // Confronta il figlio sinistro con il nodo più piccolo corrente. se (sinistra< n && arr[left] < arr[smallest]) smallest = left; // Compare the right child with the current smallest node. if (right < n && arr[right] < arr[smallest]) smallest = right; // If the current node is not the smallest // swap it with the smallest child. if (smallest != i) { int temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp; // Recursively call minHeapify on the affected subtree. MinHeapify(arr, smallest, n); } } static void Main(string[] args) { List arr = nuova lista { 10, 5, 15, 2, 20, 30 }; Console.Write('Array originale: '); foreach (int num in arr) Console.Write(num + ' '); // Esegue l'operazione di heapify sull'heap minimo. for (int i = arr.Count / 2 - 1; i>= 0; i--) MinHeapify(arr, i, arr.Count); Console.Write('
Min-Heap dopo l'operazione heapify: '); foreach (int num in arr) Console.Write(num + ' '); } }> Javascript // Define a function to perform min-heapify operation on an array function minHeapify(arr, i, n) { let smallest = i; let l = 2 * i + 1; let r = 2 * i + 2; // Check if left child is smaller than the current smallest element if (l < n && arr[l] < arr[smallest]) smallest = l; // Check if right child is smaller than the current smallest element if (r < n && arr[r] < arr[smallest]) smallest = r; // If the smallest element is not the current element, swap them if (smallest !== i) { [arr[i], arr[smallest]] = [arr[smallest], arr[i]]; minHeapify(arr, smallest, n); } } // Main function function main() { const arr = [10, 5, 15, 2, 20, 30]; // Print the original array console.log('Original array: ' + arr.join(' ')); // Perform heapify operation on the min-heap for (let i = Math.floor(arr.length / 2) - 1; i>= 0; i--) minHeapify(arr, i, arr.lunghezza); // Stampa il min-heap dopo l'operazione di heapify console.log('Min-Heap dopo l'operazione di heapify: ' + arr.join(' ')); } // Chiama la funzione main per avviare il processo main();> Produzione
Original array: 10 5 15 2 20 30 Min-Heap after heapify operation: 2 5 15 10 20 30>
La complessità temporale dell'heapify in un min-heap è O(n).
5. Operazione di ricerca sulla struttura dati Min-Heap:
Per cercare un elemento nell'heap minimo, è possibile eseguire una ricerca lineare sull'array che rappresenta l'heap. Tuttavia, la complessità temporale di una ricerca lineare è O(n), il che non è efficiente. Pertanto, la ricerca non è un'operazione comunemente utilizzata in un heap minimo.
Ecco un codice di esempio che mostra come cercare un elemento in un heap minimo utilizzando std::trova() :
C++ #include using namespace std; int main() { priority_queue , maggiore > min_heap; // esempio di heap massimo min_heap.push(10); min_heap.push(9); min_heap.push(8); min_heap.push(6); min_heap.push(4); elemento int = 6; // elemento da cercare bool trovato = false; // Copia l'heap minimo in una coda temporanea e cerca // l'elemento std::priority_queue , maggiore > temp = min_heap; while (!temp.empty()) { if (temp.top() == elemento) { trovato = true; rottura; } temp.pop(); } if (trovato) { std::cout<< 'Element found in the min heap.' << std::endl; } else { std::cout << 'Element not found in the min heap.' << std::endl; } return 0; }> Giava import java.util.PriorityQueue; public class GFG { public static void main(String[] args) { PriorityQueue min_heap = nuova PriorityQueue(); min_heap.add( 3); // inserisce elementi nella coda di priorità min_heap.offer(1); min_heap.offerta(4); min_heap.offerta(1); min_heap.offerta(6); elemento int = 6; // elemento da cercare booleano trovato = false; // Copia l'heap minimo in una coda temporanea e cerca // l'elemento PriorityQueue temp = new PriorityQueue(min_heap); while (!temp.isEmpty()) { if (temp.poll() == elemento) { trovato = true; rottura; } } if (found) { System.out.println( 'Elemento trovato nell'heap min.'); } else { System.out.println( 'Elemento non trovato nell'heap minimo.'); } } }> Python3 import heapq min_heap = [1, 2, 3, 5, 6, 7, 8, 10] # example min heap heapq.heapify(min_heap) element = 6 # element to search for found = False # Copy the min heap to a temporary list and search for the element temp = list(min_heap) while temp: if heapq.heappop(temp) == element: found = True break if found: print('Element found in the min heap.') else: print('Element not found in the min heap.')> C# using System; using System.Collections.Generic; public class GFG { public static void Main() { var minHeap = new PriorityQueue (); // esempio min heap minHeap.Enqueue(4); minHeap.Enqueue(6); minHeap.Enqueue(8); minHeap.Enqueue(9); minHeap.Enqueue(10); elemento int = 6; // elemento da cercare bool trovato = false; // Copia l'heap minimo in una coda temporanea e cerca // l'elemento var temp = new PriorityQueue (minHeap); while (temp.Count> 0) { if (temp.Peek() == elemento) { trovato = vero; rottura; } temp.Dequeue(); } if (found) { Console.WriteLine( 'Elemento trovato nell'heap minimo.'); } else { Console.WriteLine( 'Elemento non trovato nell'heap minimo.'); } } }> Javascript // Example min heap let minHeap = new PriorityQueue(); minHeap.enqueue(4); minHeap.enqueue(6); minHeap.enqueue(8); minHeap.enqueue(9); minHeap.enqueue(10); let element = 6; // Element to search for let found = false; // Copy the min heap to a temporary queue and search for the element let temp = new PriorityQueue(minHeap); while (temp.size()>0) { if (temp.peek() == elemento) { trovato = vero; rottura; } temp.dequeue(); } if (found) { console.log('Elemento trovato nell'heap min.'); } else { console.log('Elemento non trovato nell'heap minimo.'); }> Produzione
Element found in the min heap.>
Analisi della complessità :
IL complessità temporale di questo programma è O(n log n) , Dove N è il numero di elementi nella coda di priorità.
L'operazione di inserimento ha una complessità temporale di O(log n) nel peggiore dei casi perché è necessario mantenere la proprietà dell'heap. L'operazione di ricerca prevede la copia della coda prioritaria in una coda temporanea e quindi l'attraversamento della coda temporanea, che richiede O(n log n) tempo nel peggiore dei casi perché ogni elemento deve essere copiato ed estratto dalla coda e la coda con priorità deve essere ricostruita per ogni operazione.
IL complessità spaziale del programma è SU) perché memorizza N elementi nella coda di priorità e crea una coda temporanea con N elementi.
Applicazioni della struttura dei dati Min-Heap:
- Ordinamento dell'heap: L'heap minimo viene utilizzato come componente chiave nell'algoritmo di ordinamento dell'heap che è un algoritmo di ordinamento efficiente con una complessità temporale di O(nlogn).
- Coda prioritaria: Una coda con priorità può essere implementata utilizzando una struttura dati min heap in cui l'elemento con il valore minimo è sempre alla radice.
- Algoritmo di Dijkstra: Nell’algoritmo di Dijkstra, viene utilizzato un heap minimo per memorizzare i vertici del grafico con la distanza minima dal vertice iniziale. Il vertice con la distanza minima è sempre alla radice dell'heap.
- Codifica Huffman: Nella codifica Huffman, un heap minimo viene utilizzato per implementare una coda di priorità per creare un codice prefisso ottimale per un dato set di caratteri.
- Unisci array ordinati K: Dati gli array ordinati K, possiamo unirli in un unico array ordinato in modo efficiente utilizzando una struttura dati heap min.
Vantaggi della struttura dei dati Min-heap:
- Inserimento ed eliminazione efficienti : L'heap minimo consente l'inserimento e l'eliminazione rapidi di elementi con una complessità temporale di O(log n), dove n è il numero di elementi nell'heap.
- Recupero efficiente dell'elemento minimo: L'elemento minimo in un heap min è sempre alla radice dell'heap, che può essere recuperato in tempo O(1).
- Efficienza in termini di spazio: L'heap minimo è una struttura dati compatta che può essere implementata utilizzando un array o un albero binario, che la rende efficiente in termini di spazio.
- Ordinamento: L'heap minimo può essere utilizzato per implementare un algoritmo di ordinamento efficiente come l'ordinamento dell'heap con una complessità temporale di O(n log n).
- Coda prioritaria: L'heap minimo può essere utilizzato per implementare una coda con priorità, in cui l'elemento con la priorità minima può essere recuperato in modo efficiente in tempo O(1).
- Versatilità: Min heap ha diverse applicazioni in informatica, inclusi algoritmi grafici, compressione dei dati e sistemi di database.
Nel complesso, min heap è una struttura dati utile e versatile che offre operazioni efficienti, efficienza in termini di spazio e ha diverse applicazioni nell'informatica.