LabASD - Min-Heap binario

Lo scopo di questo esercizio è implementare un min-heap binario; formuleremo il problema in modo leggermente diversa da quella vista a lezione (e descritta 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 ordine rispetto alla priorità.

Attenzione: nel libro, key indica la priorità rispetto alla quale ordinare il contenuto dello heap; qui invece la priorità rispetto alla quale ordinare le informazioni nello heap è prio, mentre key rappresenta un dato satellite. Questa deviazione da quanto descritto nel libro ci tornerà utile quando implementeremo gli algoritmi di Dijkstra e di Prim).

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

Un min-heap viene rappresentato dalle strutture

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. Si deve sempre avere \(0 \leq n \leq \texttt{size}\).

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 in quanto è 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); le chiavi invece sono dati satellite, che non entrano in gioco nel mantenimento dell'ordine nello heap. Lo heap può essere realizzato mediante un array di size elementi, di cui i primi n contengono le coppie (chiave, priorità) presenti.

Attenzione: le formule che sono state descritte a lezione per individuare l'indice dei figli/del padre di un nodo \(i\) devono essere modificate per tenere conto del fatto che in C gli array sono indicizzati a partire da zero anziché da uno.

L'inserimento di una nuova coppia (chiave, priorità) avviene come in Figura 2.

La nuova coppia viene inserita alla base dello heap. Se lo heap è rappresentato in un array heap[] di dimensione size e contiene \(n\) elementi prima dell'inserimento, la nuova coppia viene inserita in 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.

L'operazione più laboriosa è la minheap_change_prio(), che modifica la priorità associata ad una chiave già presente nello heap.

Nella Figura 3 illustriamo come cambia lo heap se la priorità della chiave 0 diventa 31. Se la priorità di un nodo aumenta, occorre applicare l'operazione Heapify() vista a lezione per far "scendere" il nodo fino al livello corretto, come mostrato in figura.

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

In uno heap binario con \(n\) elementi i costi delle operazioni dovrebbero essere i seguenti:

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

Per compilare;

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

Per eseguire:

    ./minheap-main < minheap.in

oppure

    ./minheap-main minheap.in

A titolo di confronto, l'ultimo comando m presente nel file di input proposto dovrebbe stampare 6 come chiave associata alla minima priorità.

Suggerimenti

Realizzare l'operazione minheap_change_prio() in modo efficiente è complesso. Tale funzione deve modificare la priorità di una chiave già presente nello heap.

Se già sappiamo la posizione nell'array heap[] dell'elemento da modificare, la funzione può essere implementata in tempo \(O(\log n)\) nel caso peggiore. Il problema è che trovare la chiave k potrebbe richiedere tempo \(O(n)\) ("trovare la chiave" significa determinare l'indice i tale che heap[i].key == k), perché bisogna scorrere tutto lo heap.

Per trovare la chiave \(k\) in tempo \(O(1)\) si può utilizzare un secondo array pos[] contenente size elementi. pos[k] è la posizione (l'indice) dell'elemento di chiave k nell'array heap[]. Per ogni chiave k presente nello heap deve valere la proprietà:

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

Se la chiave k non è presente, si può porre pos[k] = -1.

Occorre prestare attenzione a mantenere aggiornato il contenuto di pos[] man mano che gli elementi in heap[] vengono scambiati tra loro.

File

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