DAA - Binary Heap

Esistono diversi tipi di heap, tuttavia in questo capitolo discuteremo di heap binari. UNbinary heapè una struttura dati, che sembra simile a un albero binario completo. La struttura dei dati dell'heap obbedisce alle proprietà di ordinamento discusse di seguito. In genere, un heap è rappresentato da un array. In questo capitolo, rappresentiamo un mucchio diH.

Poiché gli elementi di un heap sono archiviati in un array, considerando l'indice iniziale come 1, la posizione del nodo padre di i^th elemento può essere trovato a ⌊ i/2 ⌋. Figlio sinistro e figlio destro dii^th il nodo è in posizione 2i e 2i + 1.

Un heap binario può essere ulteriormente classificato come file max-heap o a min-heap in base alla proprietà dell'ordine.

Max-Heap

In questo heap, il valore della chiave di un nodo è maggiore o uguale al valore della chiave del figlio più alto.

Quindi, H[Parent(i)] ≥ H[i]

Min-Heap

In mean-heap, il valore della chiave di un nodo è minore o uguale al valore della chiave del figlio più basso.

Quindi, H[Parent(i)] ≤ H[i]

In questo contesto, le operazioni di base sono mostrate di seguito rispetto a Max-Heap. L'inserimento e la cancellazione di elementi in e da heap richiedono una riorganizzazione degli elementi. Quindi,Heapify la funzione deve essere chiamata.

Rappresentazione di array

Un albero binario completo può essere rappresentato da un array, memorizzando i suoi elementi utilizzando l'attraversamento dell'ordine dei livelli.

Consideriamo un heap (come mostrato di seguito) che sarà rappresentato da un array H.

Considerando l'indice di partenza come 0, utilizzando l'attraversamento dell'ordine dei livelli, gli elementi vengono mantenuti in un array come segue.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

In questo contesto, le operazioni sull'heap vengono rappresentate rispetto a Max-Heap.

Per trovare l'indice del genitore di un elemento in index i, il seguente algoritmo Parent (numbers[], i) si usa.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

L'indice del figlio sinistro di un elemento in index i può essere trovato utilizzando il seguente algoritmo, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

L'indice del figlio destro di un elemento in index i può essere trovato utilizzando il seguente algoritmo, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL