2.10 Lezione 10

Priority Queue

Una Collezione è un tipo di dati che raggruppa oggetti. Abbiamo visto, come tipo di dato, lo stack, coda, ed introduciamo ora le code a priorità.

Le code a priorità hanno un apio utilizzo e ci serve sopratutto per avere un ordinamento parziale degli elementi. Finora, la politica di rimozione è stata la seguente:

• Stack: rimuovere l'elemento aggiunto per ultimo
• Queue: rimuovere il primo elemento aggiunto
• Coda randomizzata: rimuovere un elemento random

Per quanto riguarda la coda a priorità usiamo la seguente politica:

• Priority Queue: Rimuovere il piu grande (o più piccolo) elemento.

API

				maxPQ();					//crea un pq vuota
void		insert(Key v);		//inserisce una chiave nella pq
Key 		delMax();					//ritorna e rimuove la chiave più grande
boolean	isEmpty();				//controlla se la pq è vuota
Key			max();						//ritorna la chiave più grande
int 		size();						//ritorna il numero di elementi nella pq

Applicazioni

• Simulazioni guidate da eventi
• Computazione numerica
• Intelligenza artificiale
• Reti di computers
• Sistemi operativi
• Statistica

Esempio Client

Vogliamo trovare gli items m più grandi in un flusso di n elementi, dove sia n che m sono molto grandi.

Questo tipo di problema serve come Fraud Detection, ovvero un sistema che isola le transazioni finanziarie che hanno un importo molto grande. Questa applicazione serve a risolvere il problema solo nel caso in cui non abbiamo abbastanza memoria per memorizzare tutti gli n elementi.

Implementazione

MinPQ<Transaction> pq = new MinPQ<>();

while(StdIn.hasNextLine()){
  String line = StdIn.readLine();
  Transaction transaction = new Transaction(line);
  pq.insert(transaction);
  
  if(pq.size() > m)
    pq.delMin();				//grazie a questa parte di codice possiamo mantenere nella pq solo le transazioni più grandi.
}

Ordine di crescita nella ricerca dell'elemento m più grande in uno stram di n elementi

Implementazione	tempo	Spazio
sort	n log n	n
Elementary PQ	m n	m
Binary heap	n log n	m

Implementazione con un array ordinati e non

Se utilizziamo una struttura classica, senza ordinare gli elementi, ogni volta dovrei ciclare su tutti gli elementi per trovare il massimo. Se invece usiamo una struttura che ordina gli elementi, sapremo sempre che il più grande e più piccolo si trovano agli estremi della struttura.

Operazioni

Implementazione	insert	del max	max
array non ordinato	1	n	n
array ordinato	n	1	1
goal	log n	log n	Log n

Ordine di crescita del tempo di esecuzioni per una PQ con n elementi

Il nostro obbiettivo è rendere entrambe le soluzioni efficienti, con un tempo che sia minore di n.

Soluzione: Usiamo quindi gli array parzialmente ordinati.

Binary Heaps

Un albero binario è vuoto oppure un nodo avente collegamenti ad un albero destro e sinistro.

Un albero completo è un albero perfettamente bilanciato, tranne per l'ultimo livello. In questo tipo di albero con n nodi, l'altezza è determinata da floor(lg n). Questo ci dice che l'altezza dell'albero viene incrementata solo quando n è una potenza di 2.

Binay Heap con array

Possiamo rappresentare un binary heap con un array nel seguente modo:

• Chiavi nei nodi
• Le chiavi dei nodi padri non possono essere più piccole delle chiavi di entrambi i suoi figli.

Come rappresentare il BT con un array?

• Facciamo partire gli indici da 1. In questo modo sappiamo che i figli di un nodo sono a 2k e 2k + 1.
• Prendiamo i nodi in ordine di livello.
• Non necessitiamo di link espliciti, in quanto so esattamente dove si trova il padre e figli di ogni nodo

Proprietà

Usando questo tipo di rappresentazione sappiamo che il nodo con la chiave maggiore, per come la struttura è organizzata ed ordinata, si troverà sempre a a[1].

Muoversi nell'albero

Per come è strutturata la struttura, sappiamo in ogni momento dove si trovano i "parenti" di ogni nodo:

• Il genitore del nodo nella posizione k si trova nella posizione k/2.
• I Figli del nodo nella posizione k si trovano a 2k e 2k+1.

Demo

Aggiunta di un elemento

1. Per inserire un elemento, la aggiungiamo nell'ultima posizione utile, ovvero nell'ultima posizione non ancora occupata da elementi.
2. Vado a verificare se questo inserimento risulta violare l'ordine dell'heap.
3. Se l'elemento in quella posizione viola l'ordine, effettuo lo scambio tra lui ed il nodo padre (se è maggiore).
4. Se l'ordine viola ancora l'ordine, continuo a promuovere l'elemento finchè non rispetta l'ordine dell'heap.

Rimozione del massimo

1. Per rimuovere l'elemento maggiore, effettuo lo scambio tra la prima ed ultima posizione (utile)
2. Rimuovo l'elemento massimo, che ora si trova nell'ultima posizione
3. Controllo se la radice viola l'ordine dell'heap;
4. Se viola l'ordine, effettuo il sink down, ovvero lo faccio scendere di livello: Prenderà il posto del maggiore tra i suoi figli, questo per risparmiare "scambi".
5. Continuo in questo modo finchè il nodo rispetta l'ordine.

Operazione di promozione - Swim Up

Lo Scenario è: quando una chiave diventa più grande della chiave genitore.

Per eliminare la violazione dell'ordine:

• Scambio tra il nodo attuale (figlio) ed il nodo padre
• Ripeto l'operazione finchè l'heap non risulta ordinato.

Codice java

private void swim(int k){
  while(k > 1 && less(k/2, k)){ //finchè il padre (k/2) è minore della chiave attuale
    exch(k, k/2);
    k = k/2;
  }
}

Inserimento

Aggiungo il nodo alla fine, poi swim up.

Il costo per questa operazione è al massimo 1 + lg n confronti. Questo perchè non considero tutti gli elementi, ma mi muovo verticalmente sull'albero.

Codice java

public void insert(Key x){
  pq[++n] = x;
  swim(n);
}

Operazione di Sink Down

Scenario: Una chiave diventa più piccola di quella dei figli.

Per eliminare la violazione:

• Scambiamo la chiave del genitore con quella del figlio maggiore.
• Ripetiamo finchè non si rispetta l'ordine dell'heap.

Codice java

private void sink(int k){
  while(2*k <= n){						//finchè l'ordine non è rispettato
    int j = 2*k;
    if(j < n && less(j, j+1)) // se j è minore del figlio destro, diventa il figlio destro
      j++;
    if(!less(k, j))						// verifico se il nodo k è minore del figlio j (esco se k<j)
      break;
    exch(k, j);								// scambio con il figlio maggiore calcolato nel primo if
    k = j;
  }
}

Eliminare il massimo

Scambiamo la radice con il nodo alla fine, e poi effettuiamo il sink down.

Il costo è al massimo 2 lg n confronti.

Codice java

public Key delMax(){
  Key max = pq[1];		//salvo il primo elemento (max)
  
  exch(1, n--);				//scambio con l'ultimo
  sink(1);						//sink del nuovo primo elemento
  pq[n+1] = null;			//preveniamo il loitering
    
  return max;
}

Implementazione java Binary Heap

public class MaxPQ<Key extends Comparable<Key>>{
  private Key[] pq;
  private int n;
  
  public MaxPQ(int capacity){
    pq = (Key[]) new Comparable[capacity+1];
  }
  
  public boolean isEmpty(){
    return n == 0;
  }
  
  public void insert(Key key){/*codice precedente*/}
  public Key delMax(){/*codice precedente*/}
  
  private void swim(int k){/*codice precedente*/}
  private void sink(int k){/*codice precedente*/}
  
  private boolean less(int i, int j){
    return pq[i].compareTo(pq[i]) < 0;
  }
  
  private void exch(int i, int j){
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
  }
}