h2. In completarea 'Solutiei':incalzire2020/solutii/ordonare problemei 'Ordonare':problema/ordonare

O metoda de a obtine complexitate liniara (ignorand citirea si sortarea sirului) este ca in loc sa folosim un $heap$ ($priority queue$) pentru a insera valorile date si a scoate minimul la fiecare pas, putem folosi o +lista dublu inlantuita+, astfel:

O metoda de a obtine complexitate liniara (ignorand citirea si sortarea sirului) este ca in loc sa folosim un $heap$ ({$priority queue$}) pentru a insera valorile date si a scoate minimul la fiecare pas, putem folosi o +lista dublu inlantuita+, astfel:

Lista, daca am parcurge-o de la stanga la dreapta, am vedea toate elementele din ceea ce ar fi fost inainte un $heap$, doar ca in ordine sortata. Mai mult, pe langa capetele listei, vom retine un iterator $t$ care indica nodul din lista in dreptul caruia vrem sa inseram valoarea.