Newsgroup: it.comp.programmare
Titolo: heapsort e code con priorita'

allora, premesso tutto quello che gia' si dovrebbe sapere sull'oggetto, 
mi stavo chiedendo una cosa. heapsort mi e' stato presentato come un 
algoritmo per ordinare code con priorita' evitando quindi fastidiosi 
algoritmi O(n) in fase di ricerca del minimo. ora, com'e' noto, 
l'ordinamento di una coda con priorita' implica una complessita' 
O(nlogn) per via di riempire l'heap con i dati della coda O(n), ordinare 
l'heap O(logn) e ricostruire la coda O(n). e' evidente, dall'analisi 
dell'algoritmo che heapsort e' efficiente non solo nel tempo ma anche 
nello spazio, rispetto a mergesort.
ora pero' la mia domanda e' di un altro tipo. volendo implementare una 
coda con priorita', a meno di implementarla come biscione(*), non 
sarebbe sempre e comunque piu' conveniente implementarla direttamente 
come heap? voglio dire: ogni operazione fatta su un heap ha costo 
O(logn), che sia un inserimento, una rimozione o un ordinamento 
(quest'ultimo implicito nelle prime due). perche' quindi andarsi a 
complicare la vita con una complessita' O(nlogn) quando si puo' vivere 
felici con tempo O(logn) e spazio O(n)?(**)
(*) l'idea di biscione e' nata dall'analisi dell'implementazione su 
array della classica coda di tipo fifo ovvero che per ogni inserimento 
il costo e' O(1) mentre per ogni rimozione il costo e' O(n). ora, il 
biscione e' un'idea stupida, un uovo di colombo, ma si basa sul 
principio per cui, per inserire un elemento si procede nel modo 
classico, lo si aggiunge alla fine e si aggiorna il puntatore all'ultimo 
elemento: complessita' O(1). per levare un elemento dalla coda si fa la 
stessa cosa: si ritorna il valore e si sposta avanti il puntatore alla 
testa: complessita' O(1). a questo punto si ha il tipico comportamento a 
biscione, da cui l'implementazione prende il nome, ovvero di una fila di 
dati che si muove in avanti nell'array allungandosi o accorciandosi a 
seconda delle operazioni. a questo punto, allocandogli una quantita' 
sufficientemente grande di spazio (cosa che normalmente si fa per 
evitare gli stack overflow e parenti), il biscione procedera' in avanti 
fino a che il puntatore all'ultimo elemento tocchera' la fine dello 
spazio allocato e allora interverra' un'apposita routine che, a scelta, 
a seconda del sadismo del programmatore, fara' una delle due seguenti cose:
a) copiare il biscione dalla testa alla coda all'inizio dello spazio ad 
esso dedicato riaggiornando poi i puntatori => O(n)
b) scambiare i dati contenuti nel biscione con simmetria centrale e 
invertire il senso di marcia, cosa da fare anche quando si raggiunge 
l'altro estremo per ritornare nella situazione di partenza => O(n/2) => 
O(n) asintoticamente.
secondo i principi dell'analisi ammortizzata, la coda cosi' realizzata 
ha complessita' di calcolo O(1).
(**) in realta' lo spazio dovrebbe essere theta(2n+2) perche' nel caso 
lo heap fosse, per dire, la base di dati di uno scheduler, la coda 
andrebbe scorsa ciclicamente dal nodo a priorita' massima fino a quello 
con priorita' minima (sto dicendo una mezza eresia, lo so) la qual cosa, 
pero', distruggerebbe lo heap per sua stessa natura. sarebbe quindi 
necessario, dopo aver estratto un nodo, ricreare un altro heap inserendo 
progressivamente ogni nodo levato dallo heap originario per poi ripetere 
il ciclo sul secondo heap ricostruendo un altro heap al posto che era 
stato allocato per il primo e ricominciare da capo. solo che mi tornava 
male dire che lo spazio era theta(2n+2) (il +2 e' giustificato 
dall'implementazione di heap su vettore che vuole vettore[0] vuoto e la 
radice in vettore[1] per consentire di trovare i figli vettore[2i] e 
vettore[2i+1]).
spero di essere stato abbastanza chiaro e sufficientemente delirante da 
convincervi a mandarmi solennemente affanculo. ma mi piacerebbe comunque 
avere un parere spassionato su queste mie profonde riflessioni da sei 
del mattino sul water. anche tipo "arrivi tardi, ci sono gia' arrivati".
-- 
Morpheu5

nonostante quello che potrebbe dire il mio nick, sono Juliet. Ah, quasi 
dimenticavo, Morpheu5 ha scritto:
[...]
ok, qual è la domanda? sai già che l'heap sort è perfetto per le code a 
priorità, e quindi?
-- 
  < 
http://www.reactos.com/
 >  Open source clone of Windows NT. Current
      Don't stand, REACT!      version 0.1.5. C, C++ and ASM developers
                               and beta testers are welcome!

 priorità, e quindi?
mi chiedevo perche' allora ci si ostina ad implementarle su array ed 
usare l'heap solo come base l'ordinamento...
-- 
Morpheu5

 come heap?
Penso di si'. E chi la penserebbe diversamente?
-- 
	Carlo Milanesi
 
http://digilander.libero.it/carlmila

 come heap?
infatti in genere la struttura preferita e preferibile per implementare una
coda con priorita` e` proprio uno heap.
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 Penso di si'. E chi la penserebbe diversamente?
il mio prof di dati e algoritmi :)
-- 
Morpheu5

 coda con priorita` e` proprio uno heap.
ah, ecco, volevo solo la conferma...
-- 
Morpheu5