CSES - Pienimmät alkiot

Listassa on nn kokonaislukua. Toteuta testi, jossa lasketaan listan n/10n/10 pienimmän alkion summa.

Toteuta testi kolmella tavalla:

  1. Järjestä listan sisältö ja laske listan n/10n/10 ensimmäisen alkion summa.
  2. Luo tyhjä keko, lisää listan alkiot kekoon yksi kerrallaan funktiolla heapq.heappush ja hae keosta summaan n/10n/10 pienintä alkiota.
  3. Muuta lista tehokkaasti keoksi ja hae keosta summaan n/10n/10 pienintä alkiota. Käytä tässä funktiota heapq.heapify, joka muuttaa listan keoksi lineaarisessa ajassa.

Toteuta testi niin, että n=107n=10^7 ja jokainen luku on arvottu satunnaisesti väliltä 11091 \dots 10^9. Varmista, että jokaisessa laskutavassa tulee sama vastaus.

Tässä tehtävässä saat pisteen automaattisesti, kun ilmoitat tulokset ja käyttämäsi koodin ja painat lähetysnappia.

Algoritmi 1:n kesto: s

Algoritmi 2:n kesto: s

Algoritmi 3:n kesto: s

Testissä käyttämäsi koodi: