heap concetti ed applicazioni heap • • heap = catasta condizione di heap 1. albero binario perfettamente bilanciato 2. tutte le foglie sono “a sinistra” • • ma non è un BST!! 3. ogni nodo contiene una chiave maggiore o eguale di quelle presenti negli eventuali figli non è una struttura ordinata – le visite in ampiezza e in pre- in- post-ordine non forniscono un ordinamento delle chiavi maggio 2002 ASD - Heap 2 heap? 89 89 67 66 1 68 65 66 66 5 66 67 67 4 64 68 66 1 65 2 3 66 4 67 89 67 6 67 67 67 67 67 67 maggio 2002 5 ASD - Heap 66 65 1 3 max- e min-heap • la struttura definita è detta max-heap • variante: min-heap – ogni nodo contiene una chiave minore o eguale di quelle presenti negli eventuali figli maggio 2002 6 13 13 22 23 44 27 23 32 33 24 56 81 ASD - Heap min-heap 4 operazioni su un (max-)heap • insert chiave – inserisce nuova chiave nello heap • occorre mantenere la condizione di heap • deleteMax – cancella chiave max dallo heap • occorre mantenere la condizione di heap • getMax – restituisce la chiave max nello heap • non modifica lo heap maggio 2002 ASD - Heap 5 rappresentazione degli heap • tutte le rappresentazione usate per gli alberi binarie sono ammissibili – rappresentazione collegata, eventualmente con puntatori figligenitore – rappresentazione tramite array • particolarmente efficiente maggio 2002 ASD - Heap 6 rappresentazione tramite array • ogni nodo v è memorizzato in posizione p(v ) – se v è la radice allora p(v )=0 – se v è il figlio sinistro di u allora p(v )=2p(u )+1 – se v è il figlio destro di u allora p(v )=2p(u )+2 89 67 66 maggio 2002 1 68 65 43 21 66 5 4 64 67 89 67 68 66 65 66 67 1 43 21 5 4 64 0 1 2 3 4 5 6 7 8 9 10 11 12 heap su array • vantaggi – grande efficienza in termini di spazio • l’occupazione può essere minima – facilità di navigazione • genitore i figli j – j = 2i + 1, 2i + 2 • figlio i genitore j – j = (i – 1) / 2 • svantaggio – implementazione statica • possono essere necessari progressivi raddoppiamenti/dimezzamenti dell’array di supporto maggio 2002 ASD - Heap 8 rappresentazione in Java public class Heap { public static final int DEFAULTCAPACITY = 50; protected int storage[], size; public Heap() { this(DEFAULTCAPACITY); } public Heap(int dim) { storage = new int[dim]; size = 0; } // metodi… maggio 2002 ASD - Heap 9 rappresentazione in Java/2 public boolean isLeaf(int i) { return getLeftIndex(i) >= size; } public boolean isRoot(int i) { return i == 0; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == storage.length; } maggio 2002 ASD - Heap 10 rappresentazione in Java/3 private static int getLeftIndex(int i) { return 2 * i + 1; } private static int getRightIndex(int i) { return getLeftIndex(i) + 1; } private static int getParentIndex(int i) { return (i - 1) / 2; } public String toString() {…} // segue implementazione operazioni } maggio 2002 ASD - Heap 11 algoritmi su heap • operazioni – getMax – insert – deleteMax • altri algoritmi – Array2Heap • conversione di un array in heap – HeapSort • ordinamento di un array sfruttando uno heap maggio 2002 ASD - Heap 12 getMax • il max è contenuto nella cella 0 dell’array • operazione di costo costante O(1) maggio 2002 ASD - Heap 13 insert 1. inserisci elemento alla fine dello heap 2. while (elemento non è radice) and (elemento > genitore(elemento)) 3. maggio 2002 scambia elemento con genitore ASD - Heap 14 insert/2 maggio 2002 ASD - Heap 15 insert/3 Algorithm insert(int k) { storage[size] = k; int i = size++; int j = getParentIndex(i); while(!isRoot(i)&&(storage[i]>storage[j])){ exchange(i, j); i = j; j = getParentIndex(i); } } maggio 2002 ASD - Heap 16 deleteMax 1. sostituisci primo elemento con ultima foglia ed elimina ultima foglia 2. p = radice 3. while (p non è foglia) and (p < un figlio) 4. maggio 2002 scambia p con il suo figlio maggiore ASD - Heap 17 deleteMax/2 maggio 2002 ASD - Heap 18 deleteMax/3 • conviene fare riferimento all'operazione heapify(i ) – utile in deleteMax ed in altri contesti – rende heap il sottoalbero avente radice nella cella di posto i attraverso una sequenza di scambi fra cella i e il suo figlio maggiore • i due sottoalberi di maggio 2002 i sono heap ASD - Heap 19 heapify Algorithm heapify(int i) { if(isLeaf(i)) return; j = getMaxChildIndex(i); if(storage[i] < storage[j]) { exchange(i, j); heapify(j); } } maggio 2002 ASD - Heap 20 heapify/2 public void delMax() { if(!isEmpty()) { storage[0] = storage[--size]; heapify(0); } } maggio 2002 ASD - Heap 21 costi • proporziali all’altezza dello heap (lg n ) – sia per l’inserimento sia per la cancellazione maggio 2002 ASD - Heap 22 heap e code di priorità • una coda di priorità è un tipo astratto con le seguenti operazioni – enqueue, inserimento in coda – dequeue, estrazione dalla coda dell’elemento avente priorità max • la priorità è in genere espressa da un intero • gli heap sono strutture di dati eccellenti per l’implementazione di code di priorità maggio 2002 ASD - Heap 23 altre operazioni su heap • Array2Heap – dato un array di interi costruisce uno heap con quegli interi • HeapSort – dato un array di interi ordina l’array in senso crescente maggio 2002 ASD - Heap 24 Array2Heap • dato un array arr, lo trasforma in un array che rappresenta uno heap attraverso una opportuna permutazione degli elementi • semplice algoritmo for(i = 1; i < arr.length; i++) insert(arr[i]); • costo (sfruttando l’approssimazione di Stirling del fattoriale): n lnn ! 1 i 1 lgi lgn ! ln2 ln2 (n lnn n ) (n lgn ) maggio 2002 ASD - Heap 25 Array2Heap/2 • l’algoritmo di Floyd è invece basato sull’idea di applicare l’operazione heapify ad alberi binari in cui i figli della radice sono radici di heap • vengono progressivamente “resi heap” i sottoalberi aventi la radice nel penultimo livello, quindi quelli con radice nel terz’ultimo livello ecc. – strategia bottom-up maggio 2002 ASD - Heap 26 algoritmo di Floyd 0 1 2 66 5 4 3 4 5 6 7 8 9 5 4 64 21 89 68 67 39 33 maggio 2002 12 66 5 23 11 67 23 64 45 21 89 68 67 39 33 66 67 10 45 67 4 23 64 45 21 89 68 67 39 33 ASD - Heap 27 algoritmo di Floyd/2 66 66 5 67 4 68 64 5 45 21 89 23 67 39 33 89 4 68 66 5 64 68 45 21 67 23 67 39 33 66 89 64 39 21maggio 67 2002 23 67 4 33 89 45 67 21 ASD - Heap 64 68 39 5 23 67 4 3328 45 algoritmo di Floyd/3 89 68 67 21 0 1 2 3 64 67 39 5 23 66 4 33 4 5 6 7 89 68 64 67 67 39 45 21 maggio 2002 45 ASD - Heap 8 5 9 10 11 12 23 66 4 33 29 implementazione in Java protected Heap(int[] data) {// nuovo costruttore storage = data; size = data.length; for(int i = getParentIndex(size-1); i >= 0; i--) heapify(i); } public static Heap array2heap(int[] data) { return new Heap(data); } maggio 2002 ASD - Heap 30 analisi algoritmo di Floyd • caso peggiore: ogni chiamata di heapify fa il max numero di scambi • supp. heap con n = 2k -1 nodi (albero binario completo di altezza k ) – nel penultimo livello ci sono (n +1)/4 nodi – nel terzultimo (n +1)/8 e così via maggio 2002 ASD - Heap 31 analisi algoritmo di Floyd/2 • una chiamata di heapify su un nodo a livello i provoca al più k – i scambi (op. dominanti) – uno scambio sul penultimo livello, due sul terzultimo ecc. # max di scambi = (# nodi a livello k -1)·1 + (# nodi a livello k -2)·2 + … + (# nodi a livello 2) ·(lg(n +1)-1) + (# nodi a livello 1) ·lg(n +1) = n 1 log( n 1) i 1 i 2 2i (i 1) (n 1)i 2 2i log( n 1) i log( n 1) 1 (n 1)(i 2 i 2 ) i i 2 2 maggio 2002 ASD - Heap 32 log( n 1) analisi algoritmo di Floyd/3 considerato che i 3 i 2 2i 2 ne segue che (n 1)i 2 log( n 1) log( n 1) i 2 1 0 i 2 i 1 3 3 log( n 1) 1 (n 1)( i 2 ) (n 1) i i 2 2 2 2 # max di scambi = O(n ) maggio 2002 ASD - Heap 33 applicazioni dell’algoritmo di Floyd • realizzazioni di operazioni nonstandard – eliminazione di una chiave qualunque • es.: kill di un processo dato il suo PID – O(n ) per trovare la chiave, O(1) per eliminarla, O(n ) per ripristinare la condizione di heap con l’algoritmo di Floyd • ordinamento di un array – HeapSort maggio 2002 ASD - Heap 34 HeapSort • algoritmo per l’ordinamento di un array arr basato su uno heap Algorithm HeapSort(array arr) { heap = Array2Heap(arr); for(i = n – 1; i >= 0; i--) { max = heap.getMax(); heap.delMax(); arr[i] = max; } } maggio 2002 ASD - Heap 35 HeapSort in Java public static void heapSort(int[] data) { Heap aHeap = array2heap(data); for(int i = aHeap.size - 1; i > 0; i--) { aHeap.exchange(0, i); aHeap.size--; aHeap.heapify(0); } ASD - Heap 36 } maggio 2002 aspetti pratici • codice della classe Heap • esercizio: costruire una classe MinHeap, estendendo Heap opportunamente maggio 2002 ASD - Heap 37