Struttura dei dati dell'heap

In questo tutorial imparerai cos'è la struttura dei dati dell'heap. Inoltre, troverai esempi funzionanti di operazioni di heap in C, C ++, Java e Python.

La struttura dei dati dell'heap è un albero binario completo che soddisfa la proprietà dell'heap . È anche chiamato heap binario .

Un albero binario completo è un albero binario speciale in cui

  • ogni livello, tranne forse l'ultimo, è riempito
  • tutti i nodi sono il più a sinistra possibile

La proprietà Heap è la proprietà di un nodo in cui

  • (per max heap) la chiave di ogni nodo è sempre maggiore dei suoi nodi figli e la chiave del nodo radice è la più grande tra tutti gli altri nodi;
  • (per heap min) la chiave di ogni nodo è sempre più piccola del nodo / i figlio / i e la chiave del nodo radice è la più piccola tra tutti gli altri nodi.

Operazioni su heap

Alcune delle operazioni importanti eseguite su un heap sono descritte di seguito insieme ai relativi algoritmi.

Heapify

Heapify è il processo di creazione di una struttura dati heap da un albero binario. Viene utilizzato per creare un min-heap o un max-heap.

  1. Sia l'array di input
  2. Crea un albero binario completo dall'array
  3. Inizia dal primo indice del nodo non foglia il cui indice è dato da n/2 - 1.
  4. Imposta l'elemento corrente icome largest.
  5. L'indice del bambino sinistro è dato da 2i + 1e il bambino destro è dato da 2i + 2.
    Se leftChildè maggiore di currentElement(ovvero elemento ithall'indice), impostato leftChildIndexcome maggiore.
    Se rightChildè maggiore dell'elemento in largest, imposta rightChildIndexcome largest.
  6. Scambia largestconcurrentElement
  7. Ripetere i passaggi 3-7 finché anche le sottostrutture non vengono accumulate.

Algoritmo

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Per creare un Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Per Min-Heap, entrambi leftChilde rightChilddevono essere più piccoli del genitore per tutti i nodi.

Inserisci elemento nell'heap

Algoritmo per l'inserimento in Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Inserisci il nuovo elemento alla fine dell'albero.
  2. Riempi l'albero.

Per Min Heap, l'algoritmo precedente viene modificato in modo che parentNodesia sempre inferiore a newNode.

Elimina elemento dall'heap

Algoritmo per l'eliminazione in Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Seleziona l'elemento da eliminare.
  2. Scambialo con l'ultimo elemento.
  3. Rimuovi l'ultimo elemento.
  4. Riempi l'albero.

Per Min Heap, l'algoritmo precedente viene modificato in modo che entrambi childNodessiano maggiori e minori di currentNode.

Peek (Trova max / min)

L'operazione Peek restituisce l'elemento massimo da Heap massimo o l'elemento minimo da Heap minimo senza eliminare il nodo.

Sia per Max heap che per Min Heap

 restituisce rootNode

Estratto-Max / Min

Extract-Max restituisce il nodo con il valore massimo dopo averlo rimosso da un Heap Max mentre Extract-Min restituisce il nodo con il valore minimo dopo averlo rimosso da Min Heap.

Esempi di Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java 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(); ) 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); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Applicazioni della struttura dei dati dell'heap

  • L'heap viene utilizzato durante l'implementazione di una coda di priorità.
  • Algoritmo di Dijkstra
  • Ordinamento mucchio

Articoli interessanti...