Priority Queues - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · Priority Queues L’ ADT Priority...

1

1

Priority Queues

L’ ADT Priority QueuesImplementazione di PQ mediante SequenzaAlberi HeapHeap SortAdaptable Priority Queues

2

Chiavi, Priorità, Ordinamento Totale (§ 8.1.1)

ChiaveChiave (key)oggetto assegnato ad un elemento come attributo dell’elementousato per identificare, ordinare o pesare gli elementi

Regole di confronto che definiscono un ordinamento totalesull'insieme delle chiavi:

proprietà riflessiva: k k ≤≤ kk

proprietà antisimmetrica: k1 k1 ≤≤ k2 && k2 k2 && k2 ≤≤ k1 k1 ⇒⇒ k1 = k2k1 = k2

proprietà transitiva : k1 ≤ k2 && k2 ≤ k3 ⇒ k1 ≤ k3

Coda di priorità è un insieme di coppie (chiave, valore) in cui la chiave svolge il ruolo di priorità associata al valore

2

3

Entry ADT (§ 8.1.2)

Una entry in una priority queue è una coppia (chiave, valore)Metodi:

getKey(): ritorna la chiave dell’entrygetValue(): ritorna il valore associato all’entry

Interfaccia Java:public interface Entry<K,V> {

public K key();public V value();

}

Composition design pattern: definisce un oggetto mediantecomposizione di altri oggetti

4

Comparator ADT (§ 8.1.2)

Oggetto (algoritmo) esterno all’insieme delle chiavi che fornisce le regole di confronto tra le chiavi, il criterio di ordinamento

metodo del Comparator ADT:compare(a, b) : ritorna un intero i

i negativo se a < bi =0 se a = bi positivo se a>berrore se a e b non possono essere confrontati

Una Priotity Queue ha un comparatore ausiliario

3

5

Inteface Comparable

public interface java.lang.Comparable<T> {

int compareTo(T o) ;

}

Compares this object with the specified object for order

Returns a negative integer, zero, or a positive integer as thisobject is less than, equal to, or greater than the specifiedobject

6

Inteface ComparatorIn java.util.* :public interface Comparator<T> {

int compare (T a, T b);boolean equals ( Object obj );

}definizione di un oggetto comparatore :

public class Lexicographic<T> implements Comparator<T> {public Lexicographic() { /* constructor */ }public int compare (T a, T b) { /* codice */ }

}esempio uso:

Comparator<MyString> c = new Lexicographic<MyString>();PriorityQueue<MyString,Long> pq =

new HeapPriorityQueue <MyString,Long> (c);

4

7

Esempio di Comparator per point objects

Oggetti da comparare:

/* Class representing a point in the plane with integer coordinates */public class Point2D {

protected int xc, yc; // coordinatespublic Point2D(int x, int y) { xc = x; yc = y; }

public int getX() { return xc; }public int getY() { return yc; }

}

8

Esempio di Comparator (cont.)

Lexicographic comparison of 2-D points:

public class Lexicographic<E extends Point2D>implements java.util.Comparator<E> {

public int compare(E a, E b) {if ( a.getX() != b.getX() )

return b.getX() – a.getX();else

return b.getY() – a.getY();}

}

NB : non e’ necessario che Lexicographic fornisca unaimplementazione del metodo equals() dell’interfaccia Comparator,può affidarsi al metodo equals() ereditato da Object

5

9

Priority Queue ADT (§ 8.1.3)

Una PriorityPriority QueueQueue memorizza un insieme di EntriesCiascuna entryentry è una coppia (chiave, valore)

Metodi principali dell’ ADT Priority Queueinsertinsert(k, x)(k, x) inserisce un entry con chiave k e valore xremoveMin()removeMin() rimuove e ritorna l’entry con chiave minore

Metodi addizionalimin()min() ritorna, ma non rimuove, l’entry con chiave minoresize(),size(), isEmptyisEmpty()()

10

Interface for the priority queue ADT

/** Interface for the priority queue ADT */public interface PriorityQueue<K,V> {/** Returns the number of items in the priority queue. */public int size();/** Returns whether the priority queue is empty. */public boolean isEmpty();/** Returns but does not remove an entry with minimum key. */public Entry<K,V> min() throws EmptyPriorityQueueException;/** Inserts a key-value pair and return the entry created. */public Entry<K,V> insert(K key, V value) throws InvalidKeyException;/** Removes and returns an entry with minimum key. */public Entry<K,V> removeMin() throws EmptyPriorityQueueException;}

6

11

Ordinamento con Priority Queue (§ 8.1.4)

Data una sequenza S in input, si può ordinare la sequenza Smediante priority queue PQ con un algoritmo in due fasi :

fase 1° : S PQ (estrae da S ed inserisce in PQ)fase 2°: PQ S (estrae da PQ ed inserisce in S)

1° fase: while ( ! S.isEmpty() )e = S.removeFirst()PQ.insert(e,null)

2° fase: while ( ! PQ.isEmpty() )e = PQ.removeMin()S.insertLast(e)

12


Algorithm PriorityQueueSort ( S , P ):

Input: A sequence S storing n elements, on which a total orderrelation is defined, and a priority queue, P, that compares keysusing the same total order relation

Output: The sequence S sorted by the total order relationwhile ! S.isEmpty() do

e S.removeFirst()

P.insert(e, ∅) { a null value is used }while ! P.isEmpty() do

e P.removeMin().getKey()

S.addLast(e) {the smallest key in P is added to the end of S}

7

13


Complessità diverse in corrispondenza alle diverse possibili

implementazioni di coda con priorità PQ:

PQ implementata con lista non ordinata

PQ implementata con lista ordinata

con albero heap

PQ PQ sortsort

SelectionSelection sortsort O(nO(n22))

InsertionInsertion sortsort O(nO(n22))

HeapHeap sortsort O(n log(n))O(n log(n))

14

Implementazione con Unsorted List (§ 8.2.3)

Supposto PQ implementata con seq. non ordinata:

1° while ( ! S.isEmpty() )e = S.removeFirst() O(1)PQ.insert(e, ∅) O(1)

2° while ( ! PQ.isEmpty() )e = PQ.removeMin().key() O(n)S.insertLast(e) O(1)

Costo complessivo: O(n) + O(n2) = O(nO(n22))

SelectionSelection sortsort fast insertions e slow removals

4 5 2 3 1

8

15

Analisi complessità di Selection-Sort

Analisi complessità di Selection-sort :

la coda è implementata con una sequenza non ordinata

il collo di bottiglia è costituito dalla fase-2 : ripetute rimozioni di entry con la chiave più piccola dalla coda con priorità PQ

la dimensione di PQ è inizialmente nn è diminuisce di una unità ad ogni operazione removeMin()

perciò removeMin() richiede O(n) la prima volta, O(n-1) la seconda volta, . . . ., e il costo totale è perciò :

( )2

1 2)1()12.....)1(( nOnnOiOnnO

n

i=⎟

⎠⎞

⎜⎝⎛ +

=⎟⎠

⎞⎜⎝

⎛=+++−+ ∑

=

16

Implementazione con Sorted List (§ 8.2.3)

Supposto PQ implementata con seq. ordinata:

1° while ( ! S.isEmpty() )e = S.removeFirst() O(1)PQ.insert(e, ∅) O(n)

2° while ( ! PQ.isEmpty() )e = PQ.removeMin().key() O(1)S.insertLast(e) O(1)

Complessivo: O(n2) + O(n) = O(nO(n22))

InsertionInsertion sortsort fast removals e slow insertions

1 2 3 4 5

9

17

Analisi complessità di Insertion-Sort

Analisi complessità di Insertion-sort :

Se la coda con priorità PQ è implementata con una lista ordinata, allora il costo della seconda fase si riduce a O(n) , poiché ciascuna operazione removeMin() costa O(1)

il collo di bottiglia è costituito dalla fase-1, infatti, nel caso più sfavorevole, ciascuna operazione di insert() richiede un tempo proporzionale al numero di entry che sono attualmente nella coda

il primo inserimento richiede O(1), il secondo O(2), . . . .

( )2

1 2)1())1(.....21( nOnnOiOnnO

n

i=⎟

⎠⎞

⎜⎝⎛ +

=⎟⎠

⎞⎜⎝

⎛=+−+++ ∑

=

18

SortedListPriorityQueue

10

19


20


11

21


22


12

23

In-place Insertion-sort

Invece di usare una struttura dati esterna, si può implementare il selection-sort e insertion-sort sul posto (in-place)Una porzione della sequenza di input serve come coda di prioritàCiclo nel in-place insertion-sort

si mantiene ordinata la parte iniziale della sequenzasi usano scambi invece di modoficare la sequenza

5 4 2 3 1

5 4 2 3 1

4 5 2 3 1

2 4 5 3 1

2 3 4 5 1

1 2 3 4 5

1 2 3 4 5

24

Heaps

Priority Queues implementate mediante Heap

GT cap. 8.3

2

65

79

13

25

Heap_Tree (§ 8.3)

Proprietà d'ordine

Proprietà di forma

Altezza:

Rappresentazione lineare di complete Binary Tree

HeapSort

⎣ ⎦nh log=

26

Heap (§8.3) (1)

HeapHeap: albero binario che memorizza (nei suoi nodi) una collezione di entries e che soddisfa alle due seguenti proprietà:

(1)(1) HeapHeap--OrderOrder :per ogn nodo interno vv diverso dalla radice risulta keykey(v) (v) ≥≥ keykey( ( parentparent(v) )(v) )

2

65

79

14

27

Heap (§8.3) (1)

(2) Complete (2) Complete BinaryBinary TreeTree ::siasia hh l’altezza dell’ heap

per i i = = 0, … , h 0, … , h -- 11, ci sono 22ii nodi di profondità ii

alla profondità h h -- 11, tutti i nodi interni sono alla sinistradei nodi esterni e vi è al più un nodo con un solo figlio, che deve essere un figlio sinistro

2

65

79

28

Heaps (§8.3) (2)

L’ ultimo nodo dello heap è il nodo di profondità h più a destra

Un heap con n entries, ha altezza h = ⎣ log n ⎦

2

65

79

last node

15

29

Esempio di Heap

4

6

207

811

5

9

1214

15

2516

30

Esempi che NON sono heap

16

31

ADT Complete Binary Tree (§8.3.2)

ADT Complete Binary Tree estende l’ADT Binary Tree con l’aggiunta dei seguenti due metodi :

add(e) aggiunge un nuovo nodo contenente l’elemento e in modo che l’albero risultante sia ancora un albero completo

remove() rimuove l’ultimo, ritorna l’elemento

2

65

79

add node

w

2

65

79 1w

remove node

32

Array List rappresentationof Complete Binary Tree (§8.3.2)

Possiamo rappresentare un heapcon n chiavi mediante un vettore di n+1 elementi

L’elemento 0 non è usato

L’operazione di insert avviene all’indice n+1

L’operazione removeMincorrisponde a rimozione all’indice n

Ordinamento sul posto: HeapMax

2

65

79

2 5 6 9 71 2 3 4 50

1

2 3

4 5

17

33

Priority Queue realizzata con Heap (§ 8.3.3)

Si puo’ usare un heap per implementare una coda di priorità

Si memorizza un entry (key, element) in ciascun nodo interno

Si tiene conto della posizione dell’ultimo nodo

(2, Sue)

(6, Mark)(5, Pat)

(9, Jeff) (7, Anna)

34

Insertion into a Heap (§ 8.3.3)

Il metodo insert dell’ADT priorityqueue corrisponde all’inserimento della key k nell’ heap

l’algoritmo di inserimento consiste di tre passi:

trova il nodo d’inserimento z ( il nuovo last node)

memorizza la key k in zripristina la proprietà di heap-order (upheap)

2

65

79

insertion node

z

2

65

79 1z

18

35

up-heap

Dopo l’inserimento di una nuova chiave kk , la proprietà dell’ ordinamento heap può essere violata

L’algoritmo up-heap ripristina l’ordinamento heap scambiando kklungo il cammino che va dal nodo dell’inserimento alla radice

up-heap termina quando la chiave k k raggiunge la radice o un nodo il cui padre ha una chiave minore od uguale a kk

Poiché l’heap ha altezza O(log n) , up-heap gira in O(log n)

2

15

79 6z

1

25

79 6z

36

Rimozione da un Heap (§ 8.3.3)

Il metodo removeMin dell’ ADT priority queue corrisponde alla rimozione della chiave contenuta nel nodo radice

L’algoritmo di rimozione è costituito da tre passi:

Rimpiazza la chiave del nodo radice con la chiave dell’ultimo nodo wRimuovi il nodo wRipristina la proprietà dell’’heap-order (down-heap)

2

65

79

last node

w

7

65

9w

new last node

19

37

down-heap

Dopo aver rimpiazzato la chiave del nodo radice con la chiave kkdell’ultimo nodo, la proprietà dell’heap-order può essere violataL’algoritmo down-heap ripristina la proprietà dell’ heap-orderscambiando la chiave kk lungo il cammino che va dalla radice ad un nodo fogliadown-heap termina quando la chiave kk raggiunge una foglia o un nodo i cui figli hanno una chiave maggiore od uguale a kk

Poiché l’heap ha altezza O(log n) , down-heap gira in O(log n)

7

65

9w

5

67

9w

38

Merging Two Heaps

Sono date due heap e una chiave ksi crea una nuova heap con la radice contenente k e con le due heap come sottoalberisi esegue down-heap per riprestinare la proprietà dell’ heap-order

7 key

Heap1 Heap2

7

3

58

2

64

3

58

2

64

2

3

58

4

67

20

39

Si costruisce un heap contenente n chiavi con tecnica bottom-up in log nfasi

nella fase i, coppie di heap con 2i-1 chiavi vengono fuse in heap con 2i+1-1 chiavi

Bottom-up Heap Construction (§8.3.6)

2i -1 2i -1

2i+1−1

40

Example - Bottom-up Heap Construction

costruisce (n + 1)/2 heap di un solo elemento (ipotesi n=2h-1)

ora costruisce heap con tre elementi al di sopra delle precedenti

25

1516

5

124

11

76

27

3023

1516 124 76 3023

21

41

Example (contd.)

down-heap preserva l’heap-order

15

2516

4

125

6

911

23

3027

25

1516

5

124

11

76

27

3023

42

ora forma heap con sette elementi


Example (contd.)

7

15

2516

4

125

8

6

911

23

3027

4

15

2516

5

127

6

8

911

23

3027

22

43

Example (end)

4

15

2516

5

127

10

6

8

911

23

3027

5

15

2516

7

1210

4

6

8

911

23

3027

ora forma heap con sette elementi


44

Analisi di Bottom-up Heap Construction

Il worst-case time del down-heap è visualizzato mediante i proxy-path che vanno prima a destra e poi ripetutamente a sinistra fino al fondo dell’heap (questi cammini possono differire dagli effettivi cammini di downheap)

Poiché ogni nodo è attraversato da al più due proxy path, il numero totale di nodi dei proxy-path è O(n)

Così, la costruzione bottom-up dell’heap costa O(n)

23

45

Heap-Sort (§8.3.5)

Considera una coda di priorità con n items implementata con un heap

lo spazio usato è O(n)

i metodi insert e removeMin O(log n)

i metodi size, isEmpty, e min O(1)

Usando una coda di priorità basata su heap, si puo’ fare l’ordinamento di una sequenza di n elementi in tempo:

O(n log n)

46

Ordinamento con una Priority Queue

Data una sequenza S in input, si può ordinare la sequenza S mediante PQ (Priority Queue) con un algoritmo in due fasi :

fase 1° : S PQfase 2°: PQ S in place

1° PQ.bottomUpBuild(S) O(n)

2° while ( ! PQ.isEmpty() ) O(n log n)e = PQ.removeMax()S.insertFirst(e)

24

47

In-Place Heap Sort

Usa HeapMax: un comparatore rovesciato

FaseFase 1:1: costruzione heap bottom-up :

for (i = n/2, i>=1; i--)downheap (i)

FaseFase 2:2: inizia con la sequenza vuota e muovi il confine dadestra a sinistra:

for (i=n, i >=2; i--)exchange (A[1], A[i]) //rimuove maxn = n-1 // sequenza ord. inizia da idownheap (1) // ripristina heap

48

In-Place Heap Sort – Phase 1

Use the vector representation of the heap

Phase 1:Phase 1: PQ.bottomUpBuild(S) O(n)O(n)

for (i = n/2, i>=1; i--)

downheap(i)

15 20 18 13 23 11

0 1 2 3 4 5 6

i = n/2

18

11

3

15

20 18

13 23 11

1

2

4 5 6

11

18

25

49


15 20 11 13 23 180 1 2 3 4 5 6

i = 2

20

13

3

15

20 11

13 23 18

1

2

4 5 6

13

20

15 13 11 20 23 180 1 2 3 4 5 6

i = 1 15

11

3

15

13 11

20 23 18

1

2

4 5 6

15

11

50


15 13 11 20 23 180 1 2 3 4 5 6

i = 1 15

11

3

15

13 11

20 23 18

1

2

4 5 6

15

11

11 13 15 20 23 180 1 2 3 4 5 6

3

11

13 15

20 23 18

1

2

4 5 6

Al termine del ciclo risulta un Heap

26

51


11 13 15 20 23 180 1 2 3 4 5 6

3

11

13 15

20 23 18

1

2

4 5 6

heap sequence

Phase 2Phase 2:for (i=n, i>=2; i--)

exchange (A[1], A[i])

n = n-1

downheap(1)

i = n

52


11 18

18

11

18

13 15 20 230 1 2 3 4 5 6

3

11

13 15

20 23 18

1

2

4 5 6

heap sequence

11 exchange(A[1],A[i])

18 11

18

13 15 20 230 1 2 3 4 5 6

3

18

13 15

20 23

1

2

4 5

heap sequence13

18

13

downheap(1)

27

53


13 1118 15 20 230 1 2 3 4 5 6

3

13

18 15

20 23

1

2

4 5

heap sequence

54


13 1118 15 20 230 1 2 3 4 5 6

3

13

18 15

20 23

1

2

4 5

heap sequence

13

23

23

13

23 1118 15 20 130 1 2 3 4 5 6

3

23

18 15

20

1

2

4

heap sequence

15

23

1523

exchange(A[1],A[i])

downheap(1)

28

55


20

15

15 1118 23 20 130 1 2 3 4 5 6

3

15

18 23

20

1

2

4

heap sequence15

20

exchange(A[1],A[i])

56

Adaptable priority queues (GT 8.4)

Talvolta si vuole accedere direttamente ad un entry [in O(1)] perremove( e ) ritorna vecchia ereplaceKey( e, newkey ): ritorna vecchia key di ereplaceValue( e, newval ): ritorna vecchio value di e

meccanismo per trovare posizione di e (location)

LocationAwareEntryogni entry contiene anche la posizionela posizione viene aggiornata, quando cambia

remove( e ) (log n)replaceKey( e, newkey ): (log n)replaceValue( e, newval ): O(1)

29

57

Implementazione nello heap

LocationAwareEntry è un oggetto contenente

chiavevaloreposizione dell’entry nello heap

Ciascuna posizionenello heap contiene un entryLe posizioni sonoaggiornate durante gliscambi

4 a

2 d

6 b

8 g 5 e 9 c

58

30

59

Performs up-heap bubbling

/** Performs up-heap bubbling. */protected void upHeap(Position v) {Position u;while (!T.isRoot(v)) {u = T.parent(v);if (comp.compare(key(u), key(v)) <= 0) break;swapElements(u, v);v = u;

}}

60

Performs down-heap bubbling

protected void downHeap(Position r) {while (T.isInternal(r)) {Position s; // position of the smallest childif (!T.hasRight(r))

s = T.left(r);else if (comp.compare(key(T.left(r)),

key(T.right(r))) <=0)s = T.left(r);else s = T.right(r);if (comp.compare(key(s), key(r)) < 0) {swapElements(r, s);r = s;

}else break;

}}

Priority Queues - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · Priority Queues L’ ADT Priority...

Documents

Transcript of Priority Queues - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · Priority Queues L’ ADT Priority...