[Teoria] Max heap.
Considera il problema seguente (scrivo in inglese così che non sbaglio)
Input: A positive integer \(k\) and an array \( A[1,\ldots,n] \) considting of \(n \geq k \) integers that satisfy the max-heap property, i.e. \(A\) is a max-heap.
Output: An array \(B[1,\ldots,k] \) consisting of the \(k\) largest integers of \(A\) sorted in non-decreasing order.
Design and analyze an efficient algorithm for the above problem. Ideally your algorithm should run in \(O(k \log k ) \) but the worse running time \( O( \min \{ k \log n, k^2 \} ) \) is also acceptable.
Io ho pensato di fare così.
Questo algoritmo mi prende la mia heap A, ora se \(2^e \leq k < 2^{e+1} \) per qualche \(e\) intero, abbiamo che i \(k\) elementi più grandi di \(A\) stanno tra i primi \( 2^{e+1}-1 \) indici. Quindi inserisco questi primi \(2^{e+1} - 1\) elementi in un heap temporaneo Tmp. Poi riordino Tmp in ordine crescente e prendo solo i primi \(k\) elementi di Tmp.
Ora siccome abbiamo che \( 2^{e+1} -1 \leq 2k - 1 < 2k \) risulta che il primo loop viene eseguito in un tempo \(O(k)\). Chiamo un algoritmo (Heap-sort) Che ha un tempo \(O(n \log n) \) dove \(n\) è la dimensione del array, quindi nel mio caso lo chiamo con Tmp e ha una complessità: \( O( (2^e -1 ) \log (2^e -1) ) = O(2k \log 2k) = O(k \log k) \). Poi eseguo un loop \(k\) volte di operazioni \(O(1)\), quindi ci impiega un tempo \(O(k)\). Pertanto la complessità del mio Largest-k dovrebbe essere \( O(k \log k) \). Vi sembra giusto?
Largest-k(A,k)
Questi algoritmi li abbiamo visti in corso:
Questo algoritmo prende un array in ordine casuale e lo rende un heap con la proprietà max-heap con l'algoritmo Build-Max-Heap, e poi ordina restituisce l'array in iniziale in ordine crescente con complessità \( O(k \log k ) \). Nel mio caso ho già un Build-Max-Heap quindi ci impiega \(O(1)\) invece di \(O(k)\).
Heap-sort(B,k)
Questo algoritmo mi prende un array in ordine casuale e lo rende un heap con la proprietà di Heap-max. Abbiamo visto che ha una complessità \( O(k ) \).
Build-Max-Heap(B,k)
Il seguente algoritmo prende un array \(B\), e considerando il sotto albero radicato in \(i\) in cui sia il sotto albero sinistro di \(B\) che il sotto albero destro di \(B \) hanno la proprietà di max-heap allora mi rende l'intero albero \(B\) con la proprietà max-heap. Tempo \( O(\log k) \).
Max-Heapify(B,i,k)
Input: A positive integer \(k\) and an array \( A[1,\ldots,n] \) considting of \(n \geq k \) integers that satisfy the max-heap property, i.e. \(A\) is a max-heap.
Output: An array \(B[1,\ldots,k] \) consisting of the \(k\) largest integers of \(A\) sorted in non-decreasing order.
Design and analyze an efficient algorithm for the above problem. Ideally your algorithm should run in \(O(k \log k ) \) but the worse running time \( O( \min \{ k \log n, k^2 \} ) \) is also acceptable.
Io ho pensato di fare così.
Questo algoritmo mi prende la mia heap A, ora se \(2^e \leq k < 2^{e+1} \) per qualche \(e\) intero, abbiamo che i \(k\) elementi più grandi di \(A\) stanno tra i primi \( 2^{e+1}-1 \) indici. Quindi inserisco questi primi \(2^{e+1} - 1\) elementi in un heap temporaneo Tmp. Poi riordino Tmp in ordine crescente e prendo solo i primi \(k\) elementi di Tmp.
Ora siccome abbiamo che \( 2^{e+1} -1 \leq 2k - 1 < 2k \) risulta che il primo loop viene eseguito in un tempo \(O(k)\). Chiamo un algoritmo (Heap-sort) Che ha un tempo \(O(n \log n) \) dove \(n\) è la dimensione del array, quindi nel mio caso lo chiamo con Tmp e ha una complessità: \( O( (2^e -1 ) \log (2^e -1) ) = O(2k \log 2k) = O(k \log k) \). Poi eseguo un loop \(k\) volte di operazioni \(O(1)\), quindi ci impiega un tempo \(O(k)\). Pertanto la complessità del mio Largest-k dovrebbe essere \( O(k \log k) \). Vi sembra giusto?
Largest-k(A,k)
create an empty heap Tmp,B e = floor( log_2(k) ) +1 for i =1 to 2^e -1 Tmp[i] = A[i] Heap-sort(Tmp,2^e -1) for i = 1 to k B[i] = Tmp[i] return B
Questi algoritmi li abbiamo visti in corso:
Questo algoritmo prende un array in ordine casuale e lo rende un heap con la proprietà max-heap con l'algoritmo Build-Max-Heap, e poi ordina restituisce l'array in iniziale in ordine crescente con complessità \( O(k \log k ) \). Nel mio caso ho già un Build-Max-Heap quindi ci impiega \(O(1)\) invece di \(O(k)\).
Heap-sort(B,k)
Build-Max-Heap(B,k) for i = k downto 2 exchange B[1] with B[k] Max-Heapify(B,1,i-1)
Questo algoritmo mi prende un array in ordine casuale e lo rende un heap con la proprietà di Heap-max. Abbiamo visto che ha una complessità \( O(k ) \).
Build-Max-Heap(B,k)
for i = floor(k/2) downto 1 Max-Heapify(B,i,k)
Il seguente algoritmo prende un array \(B\), e considerando il sotto albero radicato in \(i\) in cui sia il sotto albero sinistro di \(B\) che il sotto albero destro di \(B \) hanno la proprietà di max-heap allora mi rende l'intero albero \(B\) con la proprietà max-heap. Tempo \( O(\log k) \).
Max-Heapify(B,i,k)
l = left(i) r= right(i) if l <= k and B[l] > A[i] largest = l else largest = i if r <= n and B[r] > B[largest] largest = r if largest not i exchange B[i] with B[largest] Max-Heapify(B,largest,k)
Risposte
"3m0o":
Largest-k(A,k)
create an empty heap Tmp,B e = floor( log_2(k) ) +1 for i =1 to 2^e -1 Tmp[i] = A[i] Heap-sort(Tmp,2^e -1) for i = 1 to k B[i] = Tmp[i] return B
Evidentemente devo controllare un caso che mi è sfuggito ovvero se \( n \leq 2^{e+1}-1 \) oppure se \( n > 2^{e+1} -1 \). Correggo l'algoritmo
Largest-k(A,k)
create an empty heap Tmp,B e = floor( log_2(k) ) +1 if n > 2^e -1 x = 2^e-1 else x= n for i =1 to x Tmp[i] = A[i] Heap-sort(Tmp,x) for i = 1 to k B[i] = Tmp[i] return B
Il tempo di \( \operatorname{Heap-sort}(Tmp,x) \) diviene quindi \(O(x \log x ) \) ed in entrambi i casi abbiamo che \( x \leq 2k \) quindi il tempo \( O(k \log k ) \) poiché \( x \log x \leq 2k \log k + 2 k \log 2 \leq C k \log k \) e chiaramente il tempo di esecuzione di \( \operatorname{Heap-sort}(Tmp,x) \) domina il tempo di esecuzione dei due loop (rispettivamente \( O(x) = O(k) \) e \( O(k) \)).
Non ho letto tutto ma le tue premesse iniziali sono sbagliate: in un heap, il \(k\)-esimo elemento potrebbe essere tranquillamente a "profondità" \(k\).
Quello che secondo me devi fare, ma i particolari li lascio a te, è di far fare il lavoro ad un secondo heap.
Insomma, inizializzi il secondo heap con il massimo di A (o meglio con l'indice 0) e ogni volta che estrai un elemento aggiungi nell'heap i suoi figli (o meglio gli indici dei figli). L'ordine degli elementi viene fatto usando i valori di A.
Quello che secondo me devi fare, ma i particolari li lascio a te, è di far fare il lavoro ad un secondo heap.
Insomma, inizializzi il secondo heap con il massimo di A (o meglio con l'indice 0) e ogni volta che estrai un elemento aggiungi nell'heap i suoi figli (o meglio gli indici dei figli). L'ordine degli elementi viene fatto usando i valori di A.
Perché sono sbagliate le premesse?
Scusami un max-heap è un heap in cui ogni nodo padre è più grande dei due nodi figli. A è un max-heap. Quindi il nodo \( A[1] \) è il massimo in \(A\), ora il secondo più grande è uno tra \(A[2] \) e \(A[3] \). Il terzo più grande non dev'essere per forza \( A[3] \) ? Ah... forse potrebbe essere un figlio di \( A[2] \)...
Scusami un max-heap è un heap in cui ogni nodo padre è più grande dei due nodi figli. A è un max-heap. Quindi il nodo \( A[1] \) è il massimo in \(A\), ora il secondo più grande è uno tra \(A[2] \) e \(A[3] \). Il terzo più grande non dev'essere per forza \( A[3] \) ? Ah... forse potrebbe essere un figlio di \( A[2] \)...
Esattamente, il terzo potrebbe essere un figlio di \(A[2]\) e così via.
Da quello che mi hai detto implementeri così l'algoritmo
max-heap-insert inserisce un nuovo elemento in un heap-max mantenendo la heap maximality property in tempo logaritmico.
Però così mi sembra che il massimo poi estraggo sempre lo stesso Massimo quando faccio Extract-Max(H)... cioé il primo elemento di H. A meno che in Extrac-Max(H) prima di restituire il massimo (che salvo da qualche parte) non inverto il primo elemento con l'ultimo e applico Max-heapify con l'array meno l'ultimo elemento (che ora è diventato il massimo).
create empty heap B[1,...,k], Tmp B[k] = A[1] max-heap-insert(Tmp,A[2]) max-heap-insert(Tmp,A[3]) for i=k-1 downto 1 t = Extract-Max(H) B[i]=t max-heap-insert(Tmp, both t's children)
max-heap-insert inserisce un nuovo elemento in un heap-max mantenendo la heap maximality property in tempo logaritmico.
Però così mi sembra che il massimo poi estraggo sempre lo stesso Massimo quando faccio Extract-Max(H)... cioé il primo elemento di H. A meno che in Extrac-Max(H) prima di restituire il massimo (che salvo da qualche parte) non inverto il primo elemento con l'ultimo e applico Max-heapify con l'array meno l'ultimo elemento (che ora è diventato il massimo).
Certo, devi rimuovere il massimo. Comunque userei coppie (valore, indice) per Tmp. In ogni caso, perché B dovrebbe essere un heap?
"vict85":
Certo, devi rimuovere il massimo. Comunque userei coppie (valore, indice) per Tmp. In ogni caso, perché B dovrebbe essere un heap?
Si coppia (valore, indice) per codarlo in un linguaggio effettivamente così riesco poi a recuperare l'indice giusto in \(A\) e aggiungere i suoi figli tranquillamente a Tmp con \( A[2i] \) e \( A[2i+1] \). Però in pseudocodice penso vada bene anche senza l'indice. Cioè l'importante è la concezione dell'algoritmo no?
Ad ogni modo no.. B non è un heap ho sbagliato dalla fretta scrivere. Volevo dire un heap Tmp e un array B[1,...,k].
edit.
"codarlo" non l'avevo mai sentito ... 
È sanscrito.
Naaaa, lo conosco il sanscrito 
Non ti credo, però ho mentito - è vero - non è sanscrito! Questo tipo di parole entrano a far parte del tuo vocabolario quando vivi a stretto contatto con una comunità italofona che fa la stessa cosa tua che è inserita in un posto in cui non si parla italiano 
Perché vedi queste cose in inglese e poi quando stai con gli amici mischi le due lingue.
Perché vedi queste cose in inglese e poi quando stai con gli amici mischi le due lingue.
Il problema è che tu ne parli troppe
Avendo lavorato a fianco di informatici per anni, ne avevo imparato parecchie ("mecciare" su tutte
) ma "codarlo" mi è del tutto nuovo
Cordialmente, Alex
P.S.: Peraltro è vero, non conosco il sanscrito, vado a orecchio
Avendo lavorato a fianco di informatici per anni, ne avevo imparato parecchie ("mecciare" su tutte
) ma "codarlo" mi è del tutto nuovo Cordialmente, Alex
P.S.: Peraltro è vero, non conosco il sanscrito, vado a orecchio
A me sembra tu ti stia solo complicando la vita. L'input è già un Max-Heap e l'output è solo un array dimensione \(k\). Estrarre il massimo da un Max-Heap richiede tempo \(\log(n)\) e facendolo \(k\) volte si ottengono tutti gli elementi che devi mettere nel tuo output in ordine inverso. Mi sembra qualcosa come il seguente dovrebbe funzionare:
for (int i = 0; i < k; ++i) {
B[k-i-1] = A[0];
MaxHeapPop(A);
}
Ma così la complessità è \( O(k \log n ) \) e mi dice che idealmente preferisce una complessita \( O(k \log k) \).
Credo sia allora effettivamente necessario un max-heap di appoggio, mantenendo invariato \(A\). L'idea che avevi avuto mi sembra insomma quella corretta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo