LabASD - Min-Heap binario

Scopo di questo esercizio è implementare un min-heap binario; formuleremo il problema in modo leggermente diverso da quanto visto a lezione (e descritto nel libro di testo), perché questa struttura dati ci servirà in futuro.

Un min-heap è un contenitore di coppie (key, prio), di capienza massima size, dove

• key è un intero compreso tra 0 e (size-1) inclusi,

• prio è un numero reale che rappresenta la priorità associata a quella chiave. Lo heap deve mantenere la proprietà di ordinamento parziale rispetto alla priorità.

Attenzione: nel libro, key indica la priorità rispetto alla quale mantenere l’ordinamento parziale; qui invece key è un satellite, e prio è l’attributo in base al quale ordinare. La specifica adottata in questo esercizio ci servirà per implementare gli algoritmi di Dijkstra e di Prim (che vedremo più avanti).

Ogni chiave può apparire al più una volta; le priorità invece sono numeri reali arbitrari (anche negativi), e non sono soggette ad alcun vincolo. Lo heap consente di trovare efficientemente la coppia (key, prio) con prio minima.

Un min-heap viene rappresentato tramite un array di strutture HeapElem:

typedef struct {
    int key;
    double prio;
} HeapElem;

typedef struct {
    HeapElem *heap;
    int n;
    int size;
} MinHeap;

dove size è la dimensione dell’array heap[], e n è il numero di coppie (key, prio) effettivamente presenti nello heap in un dato momento. Quindi, si avrà sempre che \(0 \leq n \leq \texttt{size}\).

La struttura MinHeap rappresenta l’oggetto heap; le funzioni che agiscono su uno heap accettano come parametro un puntatore a MinHeap.

In un min-heap ogni nodo soddisfa la seguente proprietà:

La priorità di un nodo è minore o uguale a quella di entrambi i figli (se esistono)

Il file minheap.h contiene la specifica dell’interfaccia della struttura dati min-heap. Si chiede di realizzare le funzioni indicate, lasciando minheap_change_prio() per ultima perché è la più laboriosa. È sempre possibile definire ulteriori funzioni di supporto che si ritengano utili.

La Figura 1 mostra un esempio di min-heap con capienza massima size = 8 contenente \(n = 5\) elementi. L’attributo prio di ogni nodo ha valore minore o uguale a quello dei figli (se presenti). Lo heap è rappresentato da un array di size elementi, di cui i primi n contengono le coppie (chiave, priorità) effettivamente presenti, mentre i restanti hanno contenuto indefinito.

Attenzione: le formule date a lezione per individuare l’indice dei figli/del padre di un nodo \(i\) devono essere adattate al linguaggio C in cui gli array sono indicizzati a partire da zero anziché da uno.

minheap_insert()

L’inserimento di una nuova coppia (chiave, priorità) avviene dalla base dello heap. La nuova coppia viene inserita nell’elemento heap[n] e si incrementa \(n\). Successivamente, si confronta l’attributo prio del nodo appena inserito con quello del padre, effettuando uno scambio nel caso in cui venga violata la proprietà di ordine. Gli scambi con il padre vanno ripetuti fino a quando il nuovo nodo raggiunge il livello corretto (Figura 2).

minheap_change_prio()

L’operazione più laboriosa è la minheap_change_prio(), che modifica la priorità associata ad una chiave già presente nello heap. Se la priorità di un nodo aumenta, occorre applicare l’operazione move_up() (una funzione ausiliaria che viene fornita con questo esercizio; si è liberi di usarla o meno) per far “scendere” il nodo fino al livello corretto (Figura 3).

Nel caso in cui la priorità diminuisca, potrebbe rendersi necessario effettuare scambi con il padre usando un’altra funzione ausiliaria move_down() fino a quando il nuovo nodo raggiunge il livello corretto, in modo simile a quanto fatto durante l’inserimento (Figura 4).

minheap_delete_min()

Per cancellare il nodo contenente la priorità minima, occorre procedere come segue (Figura 5):

• L’ultima foglia a destra (heap[n-1]) viene copiata nella radice (heap[0], occorre prima salvare la chiave della vecchia radice, dato che andrà restituita al chiamante);

• Si decrementa il numero di nodi dello heap;

• Si confronta ed eventualmente scambia il nodo radice con il foglio di priorità minima, fino a quando il nodo radice raggiunge la profondità corretta.

Analisi

In uno heap con \(n\) elementi, le operazioni possono essere implementate con i costi asintotici riportati nella Tabella 1.

Il programma minheap-main.c contiene una funzione main() che legge da file una sequenza di comandi, uno per ogni riga, che manipolano uno heap inizialmente vuoto. I comandi sono descritti nella Tabella 2.

Per compilare;

    gcc -std=c90 -Wall -Wpedantic minheap.c minheap-main.c -o minheap-main

Per eseguire in ambiente Linux/MacOSX:

    ./minheap-main minheap.in

Per eseguire in ambiente Windows

    .\minheap-main minheap.in

Suggerimenti

Funzioni di utilità

Nel file minheap.c sono presenti delle funzioni di utilità quelle definite static, in modo che non possano essere invocate da funzioni definite fuori da quel file. Lo scopo di ciascuna è indicato nei commenti al codice.

Di particolare interesse sono le funzioni move_up(h, i) e move_down(h, i), che hanno lo scopo di far salire (rispettivamente, scendere) il nodo heap[i] fino a fargli raggiungere la posizione corretta. move_up() scambia ripetutamente il nodo con il padre, mentre move_down() scambia ripetutamente il nodo con il figlio di priorità minima; in entrambi i casi, lo scambio avviene se il nodo non occupa già la posizione corretta rispetto al padre o ai figli.

Le funzioni minheap_insert(), minheap_change_prio() e minheap_delete_min() possono essere realizzate in modo abbastanza semplice sfruttando move_up() e move_down(). L’implementazione risultante è però diversa da quella vista a lezione (e descritta nel libro): chi vuole può seguire altre strade.

Ottimizzazione di minheap_change_prio()

Implementare minheap_change_prio(h, key, newprio) in modo efficiente richiede attenzione, perché trovare il nodo dello heap contenente la chiave data key richiede tempo \(O(n)\) nel caso peggiore; la chiave, infatti, potrebbe trovarsi in qualsiasi posizione. Una volta trovato il nodo, serve tempo \(O(\log n)\) per spostarlo verso l’alto o verso il basso fino a raggiungere il nuovo livello corretto. Quindi il costo asintotico di minheap_change_prio() è dominato dalla ricerca della chiave, che è l’operazione più lenta.

Sfruttando il fatto che le chiavi appartengono all’insieme \(\{0, \ldots, \texttt{size}-1\}\), e che ogni chiave compare al più una volta, possiamo effettuare la ricerca in tempo \(O(1)\) utilizzando un secondo array pos[] di lunghezza size. pos[k] è la posizione (l’indice) dell’elemento di chiave k nell’array heap[], se presente (Figura 6). Quindi, per ogni chiave k presente nello heap deve valere la proprietà:

    heap[pos[k]].key == k

Se k non è presente, si pone pos[k] = -1.

Il contenuto di pos[] può essere mantenuto aggiornato in tempo \(O(1)\) man mano che gli elementi in heap[] vengono scambiati tra loro durante le varie operazioni sullo heap. Ciò richiede un po’ di attenzione, ma non è particolarmente problematico.

File

• minheap.c
• minheap.h
• minheap-main.c
• minheap.in (output atteso)
• minheap1.in
• minheap2.in
• minheap3.in