Algoritmi e Strutture Dati IV. Heap e Code di Priorità

Algoritmi e Strutture Dati

IV.

Heap e Code di Priorità

maggio 2002 ASD - Heap 2

heap

• heap = catasta• condizione di heap

1. albero binario perfettamente bilanciato2. ogni nodo contiene una chiave maggiore o

eguale di quelle presenti negli eventuali figli

• non memorizza un ordinamento totale – 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


Implementa tipo di dato astratto Coda di Priorità

• Insert(key)– inserisce nuovo oggetto nello heap

• occorre mantenere la condizione di heap

• deleteMax()– cancella oggetto di chiave maggiore dallo

heap• occorre mantenere la condizione di heap

• getMax()– restituisce l’oggetto di chiave max nello heap

• non modifica lo heap


rappresentazione degli heap

• tutte le rappresentazione usate per gli alberi binari 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

67 68

89

431

66 65

21 5

66 67

4 64

6566671432154

66686789

64

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;private Comparable[] storage;private int size;public Heap() {

this(DEFAULTCAPACITY);}public Heap(int dim) {

storage = new Comparable[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 int getLeftIndex(int i) {

return 2 * i + 1;}private int getRightIndex(int i) {

return getLeftIndex(i) + 1;}private int getParentIndex(int i) {

return (i - 1) / 2;}public String toString() {…}public Object clone(){…}public Object equals(){…}

}


algoritmi su heap

• operazioni– getMax()– Insert(key)– deleteMax()

• altri algoritmi– Array2Heap

• conversione di un array in heap

– HeapSort• ordinamento di un array basato su heap


getMax

• il max è contenuto nella cella 0 dell’array• operazione di costo costante O(1)

public Comparable getMax() throws Exception {

if(!isEmpty())

return storage[0];

else

throw new Exception("getMax requested to empty heap");

}


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/3public void insert(Comparable key) throws Exception{ if (this.isFull()) throw new Exception("Full heap"); else{ storage[this.size]=key; //put the new key at the end of this heap. int index = size++; int parent = getParentIndex(index); while(!isRoot(index) && (storage[index].compareTo(storage[parent])>0)) { exchange(index, parent); // sswap celle di storage index = parent; parent = getParentIndex(index); } } }


Heapify(i)

• operazione heapify(i)• considera l'albero avente radice nella

cella i e, qualora la condizione di heap non è rispettata, la ristabilisce attraverso una sequenza di scambi

• while (i non è foglia) and (key[i] < un figlio)scambia i con il suo figlio maggiore


Heapifypublic void heapify(int i) {

if(isLeaf(i))return;

else {int j = 0;try {

j = getMaxChildIndex(i);}catch(Exception e) {// only if i is a leaf.... already checked }if(storage[i].compareTo(storage[j])<0){ exchange(i, j);heapify(j);}

}


deleteMax 1

1. Sostituisci il primo elemento con l’ultima foglia

2. Elimina l’ultima foglia

1. Invoca Heapify sulla radice


deleteMax/2


Heapsort/1

• Ordinamento di un insieme di n interi

• Costruisci l’Heap inserendo gli elementi uno ad uno. Complessità: O(nlog n)

• Applica ripetutuamente deleteMax Complessità: O(n log n)


Heapsort/2

public static void heapSort(Comparable[] data) {

Heap aHeap = array2heap(data);

for(int i = aHeap.size - 1; i > 0; i--) {

aHeap.exchange(0, i);

aHeap.size--;

aHeap.heapify(0);

}

System.arraycopy(aHeap.storage, 0, data, 0, aHeap.storage.length);

}


Costruzione di un Heap in O(n)/1

1. Disponi l’insieme di elementi in un array2. For (i= indice ultimo nodo non foglia; i>=0, i--)3. Invoca heapify (i)

public static Heap array2heap(Comparable[] data) {Heap aHeap = new Heap(data.length);aHeap.size = data.length;System.arraycopy(data, 0, aHeap.storage, 0,

data.length);for(int i = aHeap.getParentIndex(aHeap.size-1); i

>= 0; i--)aHeap.heapify(i);

return aHeap;}



• Assumi n=2k-1, heap di k-1 livelli• Heapify invocata (n+1)/2 volte sui nodi dal penultimo livello fino al primo. • (n+1)/4 nodi del penultimo livello. • Heapify richiede al più 1 scambio• (n+1)/2i nodi di livello k-i-1.• Heapify su nodo di livello k-i-1 provoca al

più i-1 scambi



• Heap di n nodi ha al più lg(n) livelli • i-esimo livello dal basso:

(n+1)/2i nodi i-1 scambi compiuti da Heapify

)(2

1)1()1(

2

)1()1lg(

2

)1lg(

2

nOi

ninn

i

n

iii


Domande

• Dove si trova l’elemento più piccolo di un heap?

• Mostrare l’implementazione di una coda con una coda di priorità

• Mostrare l’implementazione di una pila con una coda di priorità

• Discutere un algoritmo che elimini un elemento qualsiasi dell’Heap in tempo O(log n)

• Discutere una struttura datio che implementi una coda di priorità che permetta di aumentare la priorità di un elemento.

Algoritmi e Strutture Dati IV. Heap e Code di Priorità

Documents

Transcript of Algoritmi e Strutture Dati IV. Heap e Code di Priorità