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)
- Codice:
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)
- Codice:
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)
- Codice:
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[i]\) che il sotto albero destro di \(B[i] \) hanno la proprietà di max-heap allora mi rende l'intero albero \(B[i]\) con la proprietà max-heap. Tempo \( O(\log k) \).
Max-Heapify(B,i,k)
- Codice:
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)
