[Teoria] Max heap.

[axpgn]

Naaaa, lo conosco il sanscrito

[3m0o]

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.

[axpgn]

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

[apatriarca]

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:

Codice:

for (int i = 0; i < k; ++i) {
    B[k-i-1] = A[0];
    MaxHeapPop(A);
}


[3m0o]

Ma così la complessità è \( O(k \log n ) \) e mi dice che idealmente preferisce una complessita \( O(k \log k) \).

[apatriarca]

Credo sia allora effettivamente necessario un max-heap di appoggio, mantenendo invariato \(A\). L'idea che avevi avuto mi sembra insomma quella corretta.