Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Heap binario

Da Wikipedia, l'enciclopedia libera.
Implementazione di un heap (min-heap) mediante Vettore

Un heap binario, è un heap sviluppato su un albero binario. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di code di priorità. L'heap binario deve sottostare alle seguenti condizioni:

  • Condizione di heap: se A è un genitore di B, allora la chiave di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap.
  • Condizione di forma: tutti i livelli dell'heap, tranne eventualmente l'ultimo, devono essere completi; se l'ultimo livello non è completo, i nodi devono essere disposti —per convenzione— a partire dall'estrema sinistra.

Dato j, indice ad un nodo della heap, si definiscono padre di j il nodo in posizione , figlio sinistro di j il nodo in posizione e figlio destro di j il nodo in posizione . Si possono quindi definire le funzioni Padre(j), FiglioSX(j), FiglioDX(j) che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di j. Spesso sono implementate come macro o funzioni in linea.

Nell'immagine a fianco è possibile osservare quanto descritto, in aggiunta si può dire che viene definito come last (ultimo) l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last ha valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.

Definizione[modifica | modifica wikitesto]

Sia U un insieme di elementi e P un insieme totalmente ordinato. Un Heap di elementi appartenenti ad U è un elemento di U* che supporta le operazioni di:

  • Inserimento: inserisci , , inserisce nell'heap H, l'elemento e con priorità p, dopo l'inserimento l'insieme mantiene le proprietà dell'heap.
  • Rimozione
  • Lettura

Code di priorità[modifica | modifica wikitesto]

Un problema classico dell'informatica è ordinare delle code di dati che possiedono una data priorità. Questo tipo di problema viene risolto utilizzando liste concatenate o alberi binari (heap).

Lista concatenata con priorità[modifica | modifica wikitesto]

Nell'implementazione attraverso liste concatenate, si ha in input un insieme di elementi (in quanto non è definita una relazione d'ordine dell'elemento ma è una proprietà intrinseca della sua priorità), e si otterrà una lista. Ad esempio se in input si ha

si otterrà una lista del tipo:

Lista head priorita.gif

La posizione nella lista non è indicativa, ma lo è la priorità di ogni singolo elemento. Il costo della gestione della lista concatenata è troppo alto per questo motivo si opta per la soluzione tramite albero binario.

Albero binario con priorità[modifica | modifica wikitesto]

In questo tipo di implementazione ogni nodo contiene sia l'elemento che la priorità dell'elemento. Un albero è heap ordinato quando per ogni nodo il valore incontrato nel nodo stesso è maggiore o uguale al valore che si incontra nei figli del suddetto nodo (per maggiori informazioni heap sort). , dove è il figlio di v.

Se un albero è heap ordinato, la radice contiene l'elemento con valore maggiore.

Albero binario heap ordinato completo[modifica | modifica wikitesto]

È un albero binario, heap ordinato, in cui tutti i livelli sono saturi, tranne l'ultimo che risulta completo da sinistra verso destra. Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di vettori, comprendenti un numero N di celle (con indici da 0 ad N-1): la prima (indice 0) resta vuota, mentre nella posizione i=1 viene memorizzata la radice. Dato quindi un nodo nella posizione i, gli eventuali figli sono nelle celle 2i (sinistro) e 2i+1 (destro).

Costruzione di un heap binario[modifica | modifica wikitesto]

Nella costruzione di un heap si hanno due tecniche differenti una con un approccio di tipo top-down (ossia si parte dalla radice) e l'altra con un approccio di tipo bottom-up (si parte dal fondo).

Rappresentazione top-down[modifica | modifica wikitesto]

Avendo in input il seguente vettore di partenza bisogna costruire un albero binario heap ordinato

A livello di analisi delle complessità si possono riscontrare due casistiche. Nel caso migliore si ha un solo confronto per l'elemento che bisogna inserire e nessuno scambio e si ottiene una complessità di ossia Nel caso peggiore ogni valore che inserisco deve essere fatto risalire fino alla radice dato che è l'elemento massimo (il costo di questa operazione dipende dall'altezza attuale dell'albero). Il numero di confronti che vengono effettuati sono uguali a cioè l'altezza dell'albero per un totale di n nodi quindi si ha una complessità di

Costruzione bottom-up[modifica | modifica wikitesto]

In un albero binario completo che ha n nodi, si hanno foglie. Si parte dalla metà dell'array che rappresenta l'heap da costruire e si verifica che ogni nodo contenga un heap ordinato. In un albero di altezza k avrò da gestire .

Si inizia a considerare il primo nodo che non è una foglia si troverà a livello k -1. A questo livello si troveranno nodi. Ogni controllo se un nodo contiene un heap ordinato sottostante utilizza 1 confronto tra i due fratelli e un confronto con il padre per un totale di 2 confronti. A livello k -1 si effettuano confronti.

Passando al livello k - 2 si effettuano quindi generalizzando al livello k - i si effettueranno ossia

Inserimento di un valore[modifica | modifica wikitesto]

Vediamo ora una rassegna dei principali metodi che sono associati ad una Priority queue, ovvero una struttura dati in cui in ogni momento è possibile associare una priorità alle entry che ne fanno parte. In primo luogo analizziamo il metodo insert, attraverso il quale, come dice il nome stesso, si inserisce un nuovo nodo all'interno dell'albero:

insert (k, x)
INPUT chiave k, entry x
OUTPUT il nodo e inserito (in posizione opportuna) nel vettore che implementa l'heap
 e <- (k,x)
 P[++last] <- e
 while ((i > 1) AND (P[⌊i/2⌋].key() > P[i].key())
 scambia P[i], P[⌊i/2⌋]
 i <- ⌊i/2⌋
 return e

nell'algoritmo appare una tecnica di scorrimento dell'heap chiamata up-heap bubbling, ovvero, dato un indice i nell'array, si controlla se le proprietà dell'albero sono verificate per i e per il suo padre, definito come la parte bassa di i/2.

Sostituzione della radice[modifica | modifica wikitesto]

Capita spesso in una struttura heap, di effettuare la sostituzione della radice con un nuovo elemento. Una volta che l'elemento viene sostituto capita che l'heap non sia più ordinato. Per questo motivo si opera il downheap, controllando a livello inferiore (2i e 2i+1) quale sia l'elemento più piccolo da promuovere alla posizione di radice. Questa procedura è ricorsiva e permette di riportare l'heap nella condizione di struttura ordinata.

Cancellazione della radice[modifica | modifica wikitesto]

Un'operazione classica di una struttura heap è la cancellazione della radice. Quest'operazione può comportare problemi a mantenere la struttura dell'heap. Il metodo più semplice è quello di sostituire il valore nella radice che si intende cancellare con il valore minimo presente nell'heap. Inizialmente il valore nella radice dell'heap viene sostituito con l'ultimo valore dell'array associato all'heap che è anche il valore più a destra nell'ultimo livello dell'albero completo. A questo punto si effettua con un approccio di tipo top down il ripristino della struttura dell'heap con una operazione di downheap che fa scorrere il valore inserito in radice lungo l'albero binario completo.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]