|
|
Capitolo 8 Code con priorità Algoritmi e Strutture Dati
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Tipo di dato CodaPriorità (1/2) Suppongo sempre che mi venga dato un riferimento diretto all’elemento da cancellare
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Tipo di dato CodaPriorità (2/2) Operazioni aggiuntive Applicazioni: gestione code in risorse condivise, gestione priorità in processi concorrenti, etc.
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Quattro implementazioni elementari Array non ordinato
Array ordinato
Lista non ordinata
Lista ordinata
Ci focalizzeremo soltanto sulle operazioni di base.
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Array non ordinato FindMin: Θ(n) (devo guardare tutti gli elementi)
Insert: O(1) (inserisco in coda)
Delete: O(1) (poiché mi viene fornito il riferimento diretto all’elemento da cancellare, lo posso cancellare in O(1) sovracopiando l’ultimo elemento)
DeleteMin: Θ(n) (devo prima cercare il minimo in Θ(n), poi lo posso cancellare in O(1))
Lo dimensiono sufficientemente grande e tengo traccia del numero n di elementi nella coda in una variabile di appoggio
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Array ordinato FindMin: O(1)
Insert: Ω(log n) ma O(n) (trovo in Θ(log n) la giusta posizione, ma poi devo fare O(n) spostamenti)
Delete: O(n) (devo fare O(n) spostamenti)
DeleteMin: O(1) (l’elemento minimo è in fondo all’array, non devo fare spostamenti)
Lo dimensiono sufficientemente grande, lo tengo ordinato in ordine decrescente e tengo traccia del numero n di elementi nella coda in una variabile di appoggio
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Lista non ordinata FindMin: Θ(n) (devo guardare tutti gli elementi)
Insert: O(1) (inserisco in coda o in testa)
Delete: O(1) (poiché mi viene fornito il riferimento diretto all’elemento da cancellare, lo posso cancellare in O(1) agendo sui puntatori)
DeleteMin: Θ(n) (devo prima cercare il minimo in Θ(n), poi lo posso cancellare in O(1))
La considero bidirezionale elemento
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Lista ordinata FindMin: O(1) (il minimo è in testa alla lista)
Insert: O(n) (trovo in O(n) la giusta posizione, e poi faccio in O(1) l’inserimento)
Delete: O(1) (agisco sui puntatori)
DeleteMin: O(1) (basta far puntare la testa della lista al secondo elemento della lista stessa)
Tengo la lista bidirezionale ordinata in ordine crescente
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Riepilogo implementazioni elementari FindMin Insert Delete DeleteMin Array non ord. Θ(n) O(1) O(1) Θ(n) Array
ordinato O(1) O(n) O(n) O(1) Lista non
ordinata Θ(n) O(1) O(1) Θ(n) Lista
ordinata O(1) O(n) O(1) O(1)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Tre implementazioni evolute d-heap: generalizzazione degli heap binari visti per l’ordinamento Heap binomiali Heap di Fibonacci (cenni)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * d-heap
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Definizione Un d-heap è un albero radicato d-ario con le seguenti proprietà:
Struttura: è completo almeno fino al penultimo livello, e tutte le foglie sull’ultimo livello sono compattate verso sinistra
Contenuto informativo: ogni nodo v contiene un elemento elem(v) ed una chiave chiave(v) presa da un dominio totalmente ordinato
Ordinamento parziale (inverso) dell’heap (min-heap): chiave(v) ≥ chiave(parent(v)) per ogni nodo v diverso dalla radice
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Esempio Heap d-ario con 18 nodi e d=3
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Proprietà Un d-heap con n nodi ha altezza Θ(logd n)
La radice contiene l’elemento con chiave minima (per via della proprietà di ordinamento a heap)
Può essere rappresentato implicitamente tramite vettore posizionale grazie alla proprietà di struttura
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Procedure ausiliarie Utili per ripristinare la proprietà di ordinamento a heap su un nodo v che non la soddisfi T(n)=O(logd n) T(n)=O(d logd n)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * findMin T(n)=O(1)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * insert(elem e, chiave k) T(n)=O(logd n) per l’esecuzione di muoviAlto
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * delete(elem e) e deleteMin T(n)= O(logd n) o O(d logd n) per l’esecuzione di muoviAlto o muoviBasso
Può essere usata anche per implementare la cancellazione del minimo, con costo O(d logd n)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * decreaseKey(elem e, chiave d) T(n)=O(logd n) per l’esecuzione di muoviAlto
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * increaseKey(elem e, chiave d) T(n)=O(d logd n) per l’esecuzione di muoviBasso
|
|
|
|
|
|
Comments