Code a priorità (Heap) Definizione Heapify (mantenimento coda a priorità) Costruire un Heap Insert, Maximum e Extract-Max Coda a priorità (Heap) • Una coda a priorità può essere rappresentato da un albero binario completo. • La chiave del padre è sempre maggiore di quella dei figli: key(i) ≤ key(parent(i)) . Albero binario completo: 16 Sono riempiti tutti i livelli eccetto possibilmente l’ultimo. Altezza=Θ(log(n)) Coda a priorità: 10 14 Il nodo a maggiore priorità (con la chiave 8 più grande) sta in cima. Nota: si può ragionare in maniera analoga quando si pone che key(i) ≥ key(parent(i)). 2 7 4 1 9 3 Heap tramite un Array • Una coda a priorità può essere implementato tramite 1 un’array (A). 16 A[PARENT(i)] ≥ A[i]. 3 2 PARENT(j) 1. return j/2 4 8 A 3 5 6 7 8 9 16 14 10 8 7 9 3 2 4 1 9 10 4 1 length[A] heap-size[A] 4 7 6 7 9 2 RIGHT(i) 1. return 2i+1 2 5 8 LEFT(i) 1. return 2i 1 10 14 n 10 … 3 Heapify (mantenimento coda a priorità) • Si sistema l’elemento A[i]: si suppone gli alberi con radice LEFT(i) e RIGHT(i) siano degli Heap. HEAPIFY(A,i) // sistema A[i] nel Heap 1. l ← LEFT(i) // figlio sx 2. r ← RIGHT(i) // figlio dx 3. if l ≤ heap-size[A] and A[l] > A[i] // cerca il maggiore fra padre e 4. then magg ← l // i due figli (se ci sono…) 5. else magg ← i 6. if r ≤ heap-size[A] and A[r] > A[magg] 7. then magg ← r 8. if magg ≠ i // il magg è uno dei due figli… 9. then scambia A[i] ↔ A[magg] 10. HEAPIFY(A,magg) Esempio Heapify • All’inizio si chiama HEAPIFY(A,2) 1 1 16 16 3 2 4 5 7 9 2 4 1 5 9 2 7 10 8 7 6 i 4 3 8 10 8 9 10 14 7 6 14 8 10 i 4 3 2 1 9 3 Esempio Heapify • Il costo in termine di tempo è nel caso peggio l’altezza dell’albero. O(h) = O(log(n)) 1 16 3 2 10 14 4 5 8 8 7 9 2 10 4 7 6 1 9 i 3 Costruire l’Heap BUILD-HEAP(A) // strategia bottom-up: dal basso verso l’alto 1. heap-size[A] ← length[A] // 2. for i ← length[A]/2 downto 1 // dalla metà in su 3. do HEAPIFY(A,i) // sotto la metà sono tutte foglie • Il costo di HEAPIFY è O(log(n)) e viene chiamato O(n) volte. Quindi un limite del caso peggiore è O(n log(n)). • In realtà, il caso peggiore può essere stimato come O(n). =2 logn h 0 logn h h n 2h1 O(h) O(n 2h1 ) O(n 2h1 ) O(2n) O(n) h 0 h 0 Rappresenta il massimo numero di sottoalberi pieni ad altezza h (avendo a disposizione n elementi) Esempio costruzione Heap 1 A 5 6 7 8 9 10 2 3 4 4 1 3 2 16 9 10 14 8 7 Si comincia da qua Foglie 1 1 4 4 3 2 3 1 4 5 8 9 14 4 7 5 i 2 10 8 10 8 9 3 1 7 6 i 16 2 3 2 9 14 16 10 8 7 6 7 9 10 Esempio costruzione Heap Strategia button-up: dal basso verso l’alto si chiama HEAPIFY su tutte i nodi interni. 1 1 4 4 3 2 3 i 1 4 5 14 8 2 4 7 5 14 10 8 10 8 9 10 8 7 6 16 9 2 10 i 1 7 6 16 9 3 2 7 9 3 Esempio costruzione Heap Strategia button-up: dal basso verso l’alto si chiama HEAPIFY su tutte i nodi interni. 1 1 i 4 16 3 2 3 16 4 5 7 9 2 4 1 5 7 9 2 10 4 7 6 8 10 8 10 8 9 10 14 7 6 14 8 3 2 1 9 3 Altre operazioni • MAXIMUM(A): ritorna l’elemento a massima priorità, ossia quello in cima. • EXTRACT-MAX(A): estrae l’elemento a massima priorità, successivamente l’Heap andrebbe sistemato • INSERT(A): inserisce un nuovo elemento nel Heap. MAXIMUM e EXTRACT-MAX MAXIMUM(A) ha un tempo di esecuzione costante, O(1) MAXIMUM(A) 1. return A[1] // restituisci l’elem. a magg. priorità, // ossia quello in cima EXTRACT-MAX(A) ha un tempo di esecuzione O(log(n)), dovuto alla chiamata HEAPIFY(). EXTRACT-MAX(A) // Estrae elemento a maggiore priorità 1. if heap-size[A] < 1 // heap vuoto? 2. then error “heap underflow” 3. max← A[1] // memorizza elem. In cima 4. A[1]← A[heap-size[A]] // metti l’ultimo elemento in cima 5. heap-size[A]← heap-size[A] – 1 // heap diminuisce di 1 elem. 6. HEAPIFY(A,1) // HEAPIFY sul 1° elem. 7. return max // restituisci l’elem. a magg. priorità HEAP-INSERT HEAP-INSERT(A, KEY) ha un tempo di esecuzione O(log(n)), nel caso peggiore si risale l’albero dalla foglia alla radice. HEAP-INSERT(A, key) // Inserisci elemento nell’Heap 1. heap-size[A]← heap-size[A] + 1 // aumenta Heap di 1 elemento 2. i← heap-size[A] // inizia dall’elem. inserito (ultimo) 3. while i > 1 and A[PARENT(i)]<key // il nuovo elem. Viene fatto 4. do A[i] ← A[PARENT(i)] // risalire… 5. i← PARENT(i) 6. A[i] ← key // fino a trovare il suo posto Inserimento in un Heap HEAP-INSERT(A, 15) key=15 L’Heap viene aumentato di un elemento. Si procede poi a risalire l’albero per trovare il suo posto. 1 1 16 16 3 2 3 14 4 5 7 9 2 4 10 8 11 10 4 9 1 8 10 14 7 6 8 8 3 2 i Nuovo elemento key = 15 2 5 8 i 9 10 4 7 6 7 9 11 1 7 3 Inserimento in un Heap HEAP-INSERT(A, 15) key=15 L’Heap viene aumentato di un elemento. Si procede poi a risalire l’albero per trovare il suo posto. 1 1 16 16 3 2 4 5 8 8 1 4 7 5 8 10 8 11 10 4 9 10 15 7 6 14 9 2 3 i 14 3 2 14 9 2 9 11 10 4 7 6 1 7 3 Considerazioni • La struttura dati Heap gestisce una coda a priorità. • Viene estratto l’elemento a maggiore priorità (es. quello con chiave maggiore) • Si può invertire la relazione con il padre, se key(i) ≥ key(parent(i)). – In questo caso l’elemento a maggiore priorità è l’elemento più piccolo • Heap-sort: algoritmo di ordinamento che usa un Heap. Si estrae ogni volta l’elemento più piccolo fino ad ottenere un vettore ordinato. Tempo O(n log(n)).