Podcast
Questions and Answers
Qual è la complessità totale dell'algoritmo HeapSort per ordinare un vettore di n elementi?
Qual è la complessità totale dell'algoritmo HeapSort per ordinare un vettore di n elementi?
In un heap massimo, una foglia non può essere situata in una posizione rappresentata da 2i.
In un heap massimo, una foglia non può essere situata in una posizione rappresentata da 2i.
True
Qual è il risultato della funzione BuildHeap su un vettore V di M elementi?
Qual è il risultato della funzione BuildHeap su un vettore V di M elementi?
V rappresenta una heap.
L'operazione di _____________________ rimuove dalla coda di priorità l'elemento con priorità più elevata.
L'operazione di _____________________ rimuove dalla coda di priorità l'elemento con priorità più elevata.
Signup and view all the answers
Abbina le operazioni alle loro descrizioni corrispondenti:
Abbina le operazioni alle loro descrizioni corrispondenti:
Signup and view all the answers
Qual è la complessità temporale dell'algoritmo di inserimento in un heap?
Qual è la complessità temporale dell'algoritmo di inserimento in un heap?
Signup and view all the answers
L'estrazione del massimo da un heap si effettua sempre rimpiazzando la radice con l'elemento più a sinistra dell'ultimo livello.
L'estrazione del massimo da un heap si effettua sempre rimpiazzando la radice con l'elemento più a sinistra dell'ultimo livello.
Signup and view all the answers
Qual è il primo passo dell'algoritmo per inserire un'etichetta in un heap?
Qual è il primo passo dell'algoritmo per inserire un'etichetta in un heap?
Signup and view all the answers
L'algoritmo di inserimento prevede un ciclo che continua finché p è maggiore di ___ e H[p] è maggiore di H[Parent(H, p)].
L'algoritmo di inserimento prevede un ciclo che continua finché p è maggiore di ___ e H[p] è maggiore di H[Parent(H, p)].
Signup and view all the answers
Abbina le seguenti fasi di estrazione del massimo con le loro descrizioni:
Abbina le seguenti fasi di estrazione del massimo con le loro descrizioni:
Signup and view all the answers
Qual è la complessità dell'algoritmo Heapify?
Qual è la complessità dell'algoritmo Heapify?
Signup and view all the answers
Il nodo contenente l'etichetta dell'ultimo nodo è sempre un heap dopo l'estrazione.
Il nodo contenente l'etichetta dell'ultimo nodo è sempre un heap dopo l'estrazione.
Signup and view all the answers
Quale valore sostituisce la radice dell'heap dopo l'estrazione?
Quale valore sostituisce la radice dell'heap dopo l'estrazione?
Signup and view all the answers
L'operazione che permette di mantenere la struttura dell'heap è chiamata ______.
L'operazione che permette di mantenere la struttura dell'heap è chiamata ______.
Signup and view all the answers
Abbina i seguenti termini con le loro descrizioni:
Abbina i seguenti termini con le loro descrizioni:
Signup and view all the answers
Quale dei seguenti passaggi è corretto nell'algoritmo HeapExtract?
Quale dei seguenti passaggi è corretto nell'algoritmo HeapExtract?
Signup and view all the answers
Heapsort funziona solo se il vettore iniziale è già un heap.
Heapsort funziona solo se il vettore iniziale è già un heap.
Signup and view all the answers
Cosa succede all'altezza dell'heap dopo l'estrazione?
Cosa succede all'altezza dell'heap dopo l'estrazione?
Signup and view all the answers
Quale delle seguenti affermazioni descrive correttamente un heap massimo?
Quale delle seguenti affermazioni descrive correttamente un heap massimo?
Signup and view all the answers
In un heap minimo, l'etichetta del genitore è minore dell'etichetta del nodo.
In un heap minimo, l'etichetta del genitore è minore dell'etichetta del nodo.
Signup and view all the answers
Qual è l'array che rappresenta l'heap massimo fornito nell'esempio?
Qual è l'array che rappresenta l'heap massimo fornito nell'esempio?
Signup and view all the answers
L'algoritmo che calcola la posizione del genitore in un heap è chiamato ___
L'algoritmo che calcola la posizione del genitore in un heap è chiamato ___
Signup and view all the answers
Abbina le operazioni con la loro descrizione corretta:
Abbina le operazioni con la loro descrizione corretta:
Signup and view all the answers
Quale delle seguenti rappresentazioni è corretta per i figli in un heap?
Quale delle seguenti rappresentazioni è corretta per i figli in un heap?
Signup and view all the answers
L'ultimo livello di un heap massimo deve essere riempito completamente da sinistra a destra.
L'ultimo livello di un heap massimo deve essere riempito completamente da sinistra a destra.
Signup and view all the answers
Cosa restituisce l'algoritmo Left(H, i) se il nodo H[i] non ha un figlio sinistro?
Cosa restituisce l'algoritmo Left(H, i) se il nodo H[i] non ha un figlio sinistro?
Signup and view all the answers
Study Notes
Heap, Heapsort, Coda di Priorità
- Obiettivi: Sviluppo di operazioni su heap, applicazioni di heap. Argomenti: definizione di heap, inserimento, estrazione, heapsort, code di priorità.
Definizione di Heap Massimo
- Un albero binario etichettato con numeri interi è un heap massimo se:
- L'albero è completo, eccetto al massimo l'ultimo livello, e l'ultimo livello è riempito da sinistra a destra.
- Per ogni nodo (eccetto la radice), l'etichetta del genitore è maggiore dell'etichetta del nodo.
Esempi di Heap Massimo
- Un esempio di albero binario che rappresenta un heap massimo è fornito nel testo (85, 75, 65, 45, 32, 12, 34, 5, 18, 31, 1, 10, 2)
Heap Minimo
- In un heap minimo, l'etichetta del genitore è minore dell'etichetta del nodo.
Rappresentazione degli Heap come Array
- Gli heap vengono rappresentati con un array in cui le etichette sono elencate livello per livello.
Operazioni su Heap
- PARENT(H, i): Restituisce la posizione del genitore di H[i], se esiste. Se non esiste, restituisce 0.
- LEFT(H, i): Restituisce la posizione del figlio sinistro di H[i], se esiste. Altrimenti, restituisce 0.
-
RIGHT(H, i): Restituisce la posizione del figlio destro di H[i], se esiste. Altrimenti, restituisce 0.
- Queste operazioni usano gli indici basati su array per rappresentare albero ( 2i per figlio sinistro, 2i+1 per figlio destro, i/2 per genitore etc).
HEAPINSERT(H, x)
- Inserisce l'elemento x nell'heap H. L'algoritmo posiziona l'elemento alla fine dell'array, poi lo fa salire finché non rispetta la condizione di heap.
- La complessità è O(log n) dove n è il numero di nodi nell'albero.
HEAPEXTRACT(H)
- Rimuove e restituisce l'elemento massimo dall'heap H. Sposta l'ultimo elemento in cima, poi lo fa scendere lungo l'albero fino a ripristinare la condizione di heap.
- La complessità è O(log n).
HEAPIFY(H, i)
- Riorganizza il sottoalbero con radice in H[i] per ripristinare la condizione di heap.
- La complessità è O(log n).
HEAPSORT
- Usa l'algoritmo BUILDHEAP per trasformare un array in un heap, quindi esegue ripetute estrazioni del massimo fino a che l'array non è ordinato. La complessità è O( n log n).
Coda di Priorità con Heap
- Una coda di priorità associa una priorità a ciascun elemento. L'estrazione restituisce l'elemento con priorità più alta. Le code di priorità possono essere implementate tramite heap.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Questo quiz tratta gli heap e le relative operazioni, come l'inserimento e l'estrazione. Verranno esplorati anche gli heap massimi e minimi, inclusa la loro rappresentazione come array e l'algoritmo Heapsort. Scopri come funzionano le code di priorità in questo contesto.
