Conplessità spaziale heap sort

[xneo]

ciao a tutti, ho dei dubbi nell'analisi della complessità spaziale di heap sort.

Ho visto che ci sono diverse implementazioni dell'algoritmo, alcune si appoggiano a strutture ausiliarie di dimensione pari alla dimensione dell'array in input che è "n".
Quindi per quanto riguarda queste implementazioni credo che l'occupazione di memoria sia Teta(n).

Ci sono altre implementazioni che sfruttano la notazione posizionale dell'array e quindi non si ha bisogno di strutture di supporto quindi la complessità sembrerebbe essere O(1).

Ma è qui che cominciano i dubbi.

Ipotizziamo che l'array abbia le proprietà di heap, cioè ogni nodo di indice i ha un elemento maggiore dei propri figli (se ne ha) che vengono individuati rispettivamente dagli indici 2i e 2i+1 (se si considera la radice con indice pari a 1).

Quindi l'algoritmo come primo passo deve scambiare il primo elemento (che contiene il massimo) con l'ultimo elemento (la posizione del massimo nell'array ordinato).
A questo punto si considera l'array fino a n-1, ma ora l'array non potrebbe più avere le proprietà di un heap; infatti non è detto che il primo elemento sia il massimo.

Per ovviare a ciò utilizzo una procedura fixHeap che opera ricorsivamente sull'array di dimensione n-1 e mi ripristina l'heap.

Ora nel caso peggiore fixHeap ha log(n-1) chiamate ricorsive innestate.

fixHeap viene chiamata n-1 volte, tuttavia la sua complessità spaziale nel caso peggiore è O(log n).

Quindi è giusto affermare in questo caso che l'occupazione di memoria è O(log n) in questo caso?
Se scrivo fixHeap in maniera iterativa allora potrei affermare che la complessità spaziale è O(1) (sempre nel caso non creo strutture dati di dimensione pari o superiore alla dimensione dell'input) ?

[hamming_burst]

dai un occhio a questi due post
- post549206.html
- viewtopic.php?f=15&t=95224

vedi se trovi risposta alle tue domande, in caso contrario ne parliamo.

[xneo]

ho letto, però non risolvono i miei dubbi.
In pratica io devo studiare la complessità spaziale di heapSort.