heap

heap

concetti ed applicazioni

maggio 2002 ASD - Heap 2

heap

• heap = catasta• condizione di heap

1. albero binario perfettamente bilanciato2. 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


heap?

67 68

89

661

66 65

66 5

66 67

4 64

67 68

89

21

66 65

3 4

66

5 6

67

6767

67 67

67 67

89

67

1

66 65


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

13 22

6

3223

13 23

33 24

44 27

56 81

min-heap


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


rappresentazione degli heap

• tutte le rappresentazione usate per gli alberi binarie sono ammissibili– rappresentazione collegata,

eventualmente con puntatori figli-genitore

– rappresentazione tramite array• particolarmente efficiente

maggio 2002

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

6767 6868

8989

434311

6666 6565

2121 55

6666 6767

44 64646464445521214343116767666665656666686867678989

4

5

6

7

8

9

10

11

3

2

1

0

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


rappresentazione in Javapublic 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…


rappresentazione in Java/2public 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;

}


rappresentazione in Java/3private 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

}


algoritmi su heap

• operazioni– getMax– insert – deleteMax

• altri algoritmi– Array2Heap

• conversione di un array in heap

– HeapSort• ordinamento di un array sfruttando uno heap


getMax

• il max è contenuto nella cella 0 dell’array

• operazione di costo costante O(1)


insert

1. inserisci elemento alla fine dello heap

2. while (elemento non è radice) and (elemento > genitore(elemento))

3. scambia elemento con genitore


insert/2


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);

}} co

dice se

mplifica

to


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. scambia p con il suo figlio maggiore


deleteMax/2


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 i sono heap


heapify

Algorithm heapify(int i) {if(isLeaf(i)) return;j = getMaxChildIndex(i);if(storage[i] < storage[j]) {

exchange(i, j);heapify(j);

}}


heapify/2

public void delMax() {if(!isEmpty()) {

storage[0] = storage[--size];heapify(0);

}}


costi

• proporziali all’altezza dello heap

(lg n )

– sia per l’inserimento sia per la cancellazione


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à


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


Array2Heap• dato un array arr, lo trasforma in un

array che rappresenta uno heap attraverso una opportuna permutazione degli elementi

• semplice algoritmofor(i = 1; i < arr.length; i++)

insert(arr[i]);• costo (sfruttando l’approssimazione di

Stirling del fattoriale):)lg()ln(

2ln1

2ln!ln

!lglg1

nnnnnn

nin

i


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


algoritmo di Floyd

5 4

66

8921

67 23

68 67

64 45

39 33

66 5 4 67 23 64 45 21 89 68 67 39 33

0 1 2 3 4 5 6 7 8 9 10 11 12

5 4

66

8921

67 23

68 67

4564

39 33


algoritmo di Floyd/2

5 4

66

8921

67 68

23 67

64 45

39 33

5 4

66

6721

89 68

23 67

64 45

39 33

5 64

66

6721

89 68

23 67

39 45

4 33

89 64

66

521

67 68

23 67

39 45

4 33

89 64

66

521

67 68

23 67

39 45

4 33


algoritmo di Floyd/3

68 64

89

521

67 67

23 66

39 45

4 33

89 68 64 67 67 39 45 21 5 23 66 4 33

0 1 2 3 4 5 6 7 8 9 10 11 12


implementazione in Java

protected Heap(int[] data) {// nuovo costruttorestorage = 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);}


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


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) =

)21

2)(1(

21

)1()1(2

1

)1log(

2

)1log(

2

)1log(

2

)1log(

2

n

i i

n

i i

n

i i

n

i i

in

ini

n


analisi algoritmo di Floyd/3

considerato che

ne segue che

# max di scambi = O(n )

23

22

i i

i0

21)1log(

2

n

i i

)1(23

)21

23

)(1(2

1)1(

)1log(

2

)1log(

2

nn

in

n

i i

n

i i


applicazioni dell’algoritmo di Floyd

• realizzazioni di operazioni non-standard– 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


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;

}}


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);

}}


aspetti pratici

• codice della classe Heap

• esercizio: costruire una classe MinHeap, estendendo Heap opportunamente

heap

Documents

Transcript of heap