Priority queue - Algoritmi e strutture dati

Ipsort è presentato più per il suo interesse teorico perché da un punto

di vista pratico quicksort è più frequentemente trovato nelle librerie,

questo perché se è vero che nel caso peggiore ipsort e mergesort si

comportano meglio di quicksort nel caso medio quicksort è migliore

perché ha delle costanti anche per insiemi piccoli di dati molto piccole.

Ipsort si basa sugli alberi binari, è particolarmente interessante la

struttura dati perché è utilizzata come struttura ausiliaria in alcuni

algoritmi, ad esempio di ricerca sui grafi, dove è necessario mantenere

un array ordinato.

Infatti il problema è proprio questo: gli algoritmi di ordinamento che

abbiamo visto fino ad oggi prendono un array non ordinato e lo

ordinano, quindi hanno un insieme di dati in input che per assunzione

non è ordinato e in output che è ordinato, ci sono anche problemi però

dove a noi non interessa avere un array ordinato in ogni momento

purché l’elemento massimo dell’array sia disponibile velocemente

quando ci serve, queste strutture sono molto dinamiche, quindi

cambiano continuamente il loro contenuto, ad esempio raccolgo un

insieme di dati, su questo insieme di dati comincio a estrarne un po' in

ordine di priorità, quindi questo presuppone che ci sia un ordinamento

di questo array, però nel frattempo o subito dopo arrivano altri dati che

vengono caricati nell’array, quindi potenzialmente scombinano

l’ordinamento di prima, io continuo però a estrarre i dati come i più

prioritari. Nella realtà succede che ci sono due serie di priorità, una

first come first serve per i clienti normali e una first come first serve

per i clienti prioritari ma se arriva un cliente prioritario mentre sono

presenti clienti normali comunque quello passa davanti, quindi la coda

è molto dinamica cioè continua a cambiare gli elementi in attesa,

quindi a differenza di un array statico in cui i dati sono stati per

esempio raccolti una volta per tutte, invece una coda non è mai statica

perché qualcuno arriva, qualcuno viene servito, qualcun altro arriva e

viene servito etc…, quindi questo problema delle code dinamiche è

quello che cerchiamo di risolvere con le priority queue.

Le code a priorità, considerate come tipo astratto, sono caratterizzate

dal fatto di possedere due metodi caratteristici che sono:

·0 l’inserzione, cioè l’arrivo di un nuovo elemento da inserire in

coda

·1 remove the maximum, è l’operazione che prende tra tutti gli

elementi in coda quello che p più prioritario, non interessa

all’algoritmo il criterio di priorità

I tipi astratti coda e stack hanno primitive che, per evitare confusione e

per chiarire bene qual è la struttura, hanno anche dei nomi diversi, per

le code parliamo quindi di enqueue e dequeue (remove the oldest, cioè

quello che è stato inserito più nel passato), invece gli stack usano

come operazioni tipiche push e pop (remove the latest, quindi l’ultimo

arrivato è anche il primo a uscire). Notiamo che le priority queue

includono le altre categorie perché con una priority queue faccio tutto,

basta che attribuisco -nel caso della queue- la priorità agli elementi

che entrando in coda una priorità decrescente man mano che arrivano,

invece nel caso della stack attribuisco una priorità crescente a quelli

che arrivano; questo però non è una mossa astuta perché mentre stack

e coda possono essere implementate con entrambe le operazioni in

tempo costante, le priority queue non possono essere implementante

con entrambe le operazioni in tempo costante, una delle due o

entrambe richiederanno un tempo maggiore, non è possibile

implementare un generico remove the maximum in tempo costante

Vediamo due modi elementari di implementare una priority queue. Le

priority queue richiedono un tempo almeno lineare per almeno una

delle due operazioni, nelle versioni elementari, invece ce n’è una più

astuta che richiede un tempo logaritmico per entrambe le operazioni

Elementary implementation I

Consideriamo un array non ordinato gestito con la logica dello stack,

cioè man mano che arriva un elemento lo inserisco nel primo posto

disponibile, cioè quello più alto non occcupato, quindi tengo memoria

di quanti elementi sono presenti nell’array e, se qualcuno mi chiede di

inserire un nuovo elemento, lo metto nella prima posizione libera

successiva, cioè nell’immagine dopo il 3:

quindi con un array non ordinato l’operazione insert avviene al top,

cioè al primo elemento disponibile, quindi il tempo richiesto è costante

( ) infatti c’è una variabile ausiliaria che mi dice che l’elemento va

inserito nel primo spazio vuoto disponibile, devo solo incrementare la

dimensione del punto di riempimento e mettere lì l’elemento.

L’operazione di remove the max invece, siccome io non so in che

ordine sono arrivati gli elementi, presuppone che io visiti tutto l’array e

trovi l’elemento che ha il valore massimo in quel momento, devo far

scorrere il mio array, trovare l’elemento e, per mantenere l’array

compatto, scambio il massimo che ho trovato con il top e poi riduco di

1 l’array perché voglio togliere il massimo, quindi il tempo richiesto è

. Nell’esempio precedente abbiamo che il valore massimo è 8,

scorro l’array, trovo che 8 è il massimo, lo scambio con 3 e tolgo

l’ultimo elemento, cioè l’8 scambiato con il 3.

Questa implementazione è veloce e se ho delle priority queue piccole

posso anche pensare di fare delle operazioni del genere perché come

sempre degli algoritmi asintoticamente svantaggiosi potrebbero avere

delle implementazioni e delle costanti su piccoli valori che li rendono

invece vantaggiosi su dimensioni piccole.

Elementary implementation II

In questo caso io mantengo ordinato l’array in modo tale che

l’elemento più prioritario sia sempre al top ma ogni volta che devo

inserire un elemento vado a inserirlo cercando la posizione dove c’è

l’elemento massimo, quindi perché mediamente trovo la posizione

dell’elemento nuovo a metà dell’array visto che questo è ordinato,

dovrò far scorrere tutti gli elementi che seguono ovviamente, quindi

sto usando l’insertion sort ma il vettore lo mantengo ordinato, è un

insertion sort che non viene fatto su tutto il vettore ma che cresce man

mano nel tempo.

Prendere il massimo diventa più veloce perché visto che il vettore è

ordinato allora il massimo è in cima, prendo il massimo e riduco di 1 la

dimensione dell’array perché non voglio conservarlo, quindi nel

prendere il massimo .

Notiamo che negli ultimi due elementary implementation l’ordine di

complessità è sempre costante per una delle due operazioni

(inserimento o rimozione) e lineare per l’altra operazione.

The binary heap

Essa è una struttura concreta che consente di implementare in modo

efficiente entrambe le operazioni, quindi sia l’inserimento che

l’estrazione del massimo sono implementati in modo da richiedere

asintoticamente .

Ci sono strutture dati che sono usate prevalentemente per

l’inserimento e altre usate prevalentemente per le estrazioni, quindi ci

interesserà essere veloci in una o nell’altra operazione, però

inserimento ed estrazioni devono essere equilibrati perché se inserisco

solo in coda prima o poi esplode, se toglo e basta arriva a zero come

dimensioni e verificare che la coda è vuota richiede sempre un tempo

costante, quindi in questi algoritmi inserimento ed estrazione devono

essere equilibrati e in generale quando queste strutture sono usate

come strutture ausiliarie l’inserimento e la cancellazione avvengono

esattamente lo stesso numero di volte perché la coda parte vuota e

finisce vuota per esigenze degli algoritmi di cui sono strutture

ausiliarie.

La binary heap che garantisce inserimenti e cancellazioni in ordine

log(N) è considerata più che efficiente

La binary heap è il nome della struttura concreta mentre quello che

andiamo a implementare come tipo astratto è la priority queue. L’idea

consiste nel memorizzare la coda in una struttura che è equivalente a

un albero, la rappresentazione ad albero è comoda per descrivere

come la struttura viene organizzata ma non si usa un albero binario ma

un array, quindi si memorizza una struttura ad albero all’interno di un

array con opportune convenzioni e regole per la memorizzazione,

quindi non si memorizzano i puntatori agli elementi:

Questo però richiede diversi passaggi, ad esempio richiede di definire

cosa si intende per heap-ordered della binary heap, se guardiamo

l’albero possiamo dire che una struttura si dice heap-ordered se ogni

nodo è più grande (in questo caso intendiamo l’ordine alfabetico) dei

suoi figli, questa proprietà impone una certa struttura all’intero albero.

Nella descrizione dell’albero c’è scritto anche “complete”, chiamiamo

completo quest’albero se tutti i livelli dell’albero sono riempiti tranne

l’ultimo. Il primo livello è riempito per definizione, il secondo livello è

riempito perhè ci sono 2 nodi (2^1), il terzo livello contiene 4 nodi

(2^2=4), ogni livello quindi deve contenere 2^(n-1) nodi tranne

l’ultimo.

Un albero binario completo può essere memorizzato in un array senza

riportare esplicitamente i puntatori, però in questo caso la completezza

è una proprietà critica, in un array possiamo quindi rappresentare solo

gli alberi binari completi. Per costruire questa rappresentazione devo

visitare l’albero, cioè enumerare tutti i suoi nodi, la visita di una

struttura dati, per le strutture dati non elementari, può essere fatta in

molti modi, quindi ad esempio un albero può essere visitato in ordine

anticipato, in ordine differito, in ordine simmetrico e anche in heap-

order (o level order), cioè un livello per volta, quindi prendo il primo

livello T, poi scendo e faccio S e R, poi vado al terzo livello e faccio P,

N, O, A etc…

Questa visita ci permette di inserire gli elementi che estraiamo in un

array in un modo che permette anche di predire la loro posizione in

quanto elementi di un albero

Vediamo cosa succede se facciamo una visita level order di un albero

binario completo: la visita in level order la possiamo fare sempre, è

richiest