Esame: Heap e code di priorità

Che cos'è un heap?

Un heap è una struttura dati ad albero che soddisfa la proprietà di heap, dove ogni nodo è maggiore (max heap) o minore (min heap) dei suoi figli.

Proprietà principale di un max heap?

In un max heap, per ogni nodo, il valore è sempre maggiore o uguale ai valori dei suoi figli.

Proprietà principale di un min heap?

In un min heap, per ogni nodo, il valore è sempre minore o uguale ai valori dei suoi figli.

Heap vs Albero binario

Un heap è un albero binario completo, ma non ogni albero binario è un heap. Gli heap rispettano specifiche proprietà di ordinamento.

Qual è l'operazione principale negli heap?

L'operazione principale è l'heapify, che mantiene la proprietà dell'heap dopo l'inserimento o l'estrazione di un nodo.

Come si rappresenta un heap in un array?

In un array, per un nodo in posizione $\displaystyle i$: il figlio sinistro è in $\displaystyle 2i + 1$, il figlio destro in $\displaystyle 2i + 2$, e il padre è in $\displaystyle \frac{i-1}{2}$.

Vero o falso: Gli heap possono avere nodi non pieni.

Vero. Gli heap non devono essere completamente pieni, ma devono mantenere la loro struttura ad albero completo.

Che cos'è l'heapify?

L'heapify è un'operazione che ripristina la proprietà di heap in un nodo e i suoi figli.

Esempio di max heap: 10, 5, 3

10 è il nodo radice. 5 e 3 sono figli. Completando l'heap: 10, 5, 3, 2.

Quale operazione rimuove il nodo radice?

L'operazione di estrazione rimuove il nodo radice e ripristina la proprietà di heap attraverso l'heapify.

Definizione di heap completo.

Un heap completo è un albero binario in cui tutti i livelli sono completamente riempiti eccetto, eventualmente, l'ultimo livello.

Quali sono le applicazioni comuni degli heap?

Ordinamento (Heap Sort), implementazioni di code di priorità, gestione della memoria.

Heap: struttura dati statica o dinamica?

Dinamica. Gli heap possono cambiare dimensione durante l'esecuzione di un programma.

Che cos'è la complessità di inserimento in un heap?

La complessità di inserimento in un heap è $\displaystyle O( ext{log } n)$.

Qual è la complessità di estrazione?

La complessità di estrazione dalla cima dell'heap è $\displaystyle O( ext{log } n)$.

Vero o falso: Gli heap sono sempre bilanciati.

Falso. Gli heap seguono una struttura completa ma non garantiscono un bilanciamento come gli alberi AVL.

Definizione di una coda di priorità

Una struttura dati che gestisce una collezione di elementi, ciascuno con una priorità. Gli elementi con priorità più alta vengono estratti prima.

Utilizzo principale delle code di priorità

Gestione di eventi in tempo reale, pianificazione di processi nei sistemi operativi, implementazione degli algoritmi di Dijkstra e A*.

Cosa distingue una coda di priorità da una coda normale?

Una coda normale gestisce gli elementi in ordine FIFO, mentre una coda di priorità estrae gli elementi in base alla priorità assegnata.

True or False: Le code di priorità possono utilizzare heap per la loro implementazione.

Vero: Gli heap, specialmente gli heap binari, sono comunemente usati per implementare efficacemente le code di priorità.

Come si inserisce un elemento in una coda di priorità?

L'elemento viene aggiunto e poi il heap viene riordinato per mantenere la proprietà di priorità, di solito tramite una 'percolazione' verso l'alto.

Esempio di utilizzo di una coda di priorità

Gestione di processi in un sistema operativo. Processi con priorità più alta vengono eseguiti prima di quelli con priorità più bassa.

Quali sono le operazioni principali su una coda di priorità?

- Inserimento - Estrazione del massimo/minimo - Aggiornamento della priorità - Controllo della priorità

Cosa succede quando si estrae un elemento da una coda di priorità?

L'elemento con la priorità più alta viene rimosso e l'heap viene ristrutturato per mantenere la proprietà di heap.

Fill in the blank: In una coda di priorità, gli elementi vengono estratti in base alla loro ______.

priorità.

Confronto: Coda normale vs Coda di priorità

Coda normale: FIFO; Coda di priorità: estrae in base alla priorità.

Quale struttura dati è comunemente usata per le code di priorità?

Heap binario, utile per garantire operazioni logaritmiche efficienti.

Cause → Effetto: Aggiunta di un elemento con alta priorità.

Il nuovo elemento sposta gli elementi esistenti, aumentando il tempo di estrazione per quelli a bassa priorità.

Vantaggio delle code di priorità rispetto alle code normali?

Flessibilità nella gestione degli elementi in base alla loro importanza, non solo all'ordine di arrivo.

Cosa accade se due elementi hanno la stessa priorità?

L'ordine di estrazione dipende dall'implementazione specifica, ma normalmente segue l'ordine di inserimento.

Domanda: Le code di priorità possono essere implementate con array?

Sì, ma non sono efficienti come gli heap per operazioni di inserimento ed estrazione.

Esempio di priorità numerica: 5, 3, 8

Estrazione: 8 (massimo), seguito da 5 e 3.

Cos'è l'operazione di inserimento in un heap?

L'inserimento in un heap comporta l'aggiunta di un nuovo elemento. Si posiziona alla fine e si effettua un "heapify up" per mantenere la struttura.

Come si estrae l'elemento massimo da un heap?

L'elemento massimo è la radice. Si sostituisce con l'ultimo elemento e si esegue un "heapify down" per ripristinare la proprietà dell'heap.

Vero o falso: Un heap è sempre bilanciato.

Falso. Un heap è completo, non necessariamente bilanciato, ma ogni livello è riempito da sinistra a destra.

Qual è la complessità dell'inserimento in un max heap?

La complessità è $\displaystyle O( ext{log } n)$ poiché si può dover risalire fino alla radice.

Descrivi brevemente l'operazione di aggiornamento in un heap.

L'aggiornamento implica modificare il valore di un nodo e poi eseguire un "heapify up" o "heapify down" per mantenere la struttura.

Confronta l'estrazione di un elemento da un max heap e da un min heap.

Max heap estrae il massimo, min heap estrae il minimo. Entrambi hanno complessità $\displaystyle O( ext{log } n)$.

Qual è l'effetto di un 'heapify down'?

Ripristina la proprietà dell'heap dopo l'estrazione, confrontando un nodo con i figli e scambiando se necessario.

Esempio pratico: Iniziamo con 10, 20, 30 in un max heap. Aggiungiamo 25.

Heap: 30, 20, 10, 25. Si posiziona 25 e si confronta con 20, poi si scambia.

Quando si usa 'heapify up'?

Si usa durante l'inserimento o l'aggiornamento di un nodo per mantenere la proprietà dell'heap.

Qual è la complessità dell'operazione 'heapify down'?

La complessità è $\displaystyle O( ext{log } n)$, poiché si può scendere fino all'ultima foglia.

Cos'è un heap completo?

Un heap completo è un albero binario in cui ogni livello, tranne l'ultimo, è pieno. L'ultimo livello è riempito a sinistra.

Fill in the blank: L'operazione di _________ ripristina la proprietà dell'heap dopo una modifica.

heapify

Applicazioni degli heap nel mondo reale?

1. Gestione delle code di stampa. 2. Implementazione di algoritmi di Ordinamento. 3. Simulazioni e giochi.

Heap vs. Array: differenze?

1. Struttura dati dinamica vs. statica. 2. Accesso non sequenziale vs. sequenziale. 3. Complessità di inserimento: $\displaystyle O( ext{log } n)$ vs. $\displaystyle O(n)$.

Vero o falso: gli heap sono sempre bilanciati.

Falso. Gli heap non garantiscono un bilanciamento perfetto come gli alberi bilanciati.

Esempio di codice per una coda di priorità?

Utilizzo di un heap per gestire le priorità: ```python import heapq coda = [] heapq.heappush(coda, (priorità, elemento)) ```

Qual è la complessità dell'estrazione dal heap?

La complessità dell'estrazione dal heap è $\displaystyle O( ext{log } n)$.

Cause ed effetti: heap in algoritmi di Dijkstra?

Causa: utilizzo di un heap per gestire i nodi. Effetto: migliora l'efficienza dell'algoritmo.

Utilizzo delle code di priorità nei sistemi operativi?

Gestione dei processi: - Scheduling - Assegnazione della CPU - Gestione delle risorse

Esempio di applicazione pratica di heap?

Gestione delle chiamate in un call center, dove le chiamate vengono servite in base alla priorità.

Vero o falso: gli heap possono essere implementati come array.

Vero. Gli heap possono essere implementati usando array, sfruttando indici per posizioni.

Qual è la complessità della costruzione di un heap?

La complessità della costruzione di un heap è $\displaystyle O(n)$.

Heap e alberi binari: somiglianze?

1. Entrambi sono strutture ad albero. 2. Heap è un albero binario completo. 3. Entrambi supportano operazioni di inserimento e cancellazione.

Come si scambia un elemento in un heap?

Scambia l'elemento con il suo genitore, ripetendo finché la proprietà dell'heap è rispettata.