Python stazaCjelina 5 · Strukture podataka (napredno)Lekcija 32

Hrpa (heapq): uvijek najmanji

Kad stalno trebaš najmanji (ili najveći) element skupa koji se mijenja, hrpa ga daje u trenu. Zadnja lekcija Python staze.

Pythonoko 45 minuta3 zadatka za evaluator

1Uvijek trebam najmanji

Neki zadaci stalno traže najmanji element skupa koji se mijenja: dodamo nešto, uzmemo najmanji, opet dodamo… Svaki put pozvati min(lista) i remove znači proći cijelu listu. Za 100 000 koraka to je predugo.

Hrpa (engl. heap) je lista složena tako da je najmanji element uvijek na mjestu 0, a dodavanje i uzimanje traju samo oko log N koraka. U Pythonu je u modulu heapq.

NaredbaŠto radi
import heapquvozi modul
h = []prazna hrpa (obična lista)
heapq.heappush(h, x)dodaje x
heapq.heappop(h)skida i vraća najmanji element
h[0]gleda najmanji element
heapq.heapify(lista)postojeću listu pretvara u hrpu
x–
h–
prvi–
drugi–
Klikni „Sljedeći korak“ i prati što se događa.
Pazi

Hrpa nije sortirana lista! Samo je h[0] sigurno najmanji. Ne ispisuj h u nadi da je poredan.

2A kad trebam najveći?

heapq zna samo najmanji. Trik: u hrpu spremamo negativne brojeve. Najmanji negativni broj je najveći pravi broj.

Program
import heapq
h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, -x)
print(-heapq.heappop(h))
print(-heapq.heappop(h))
Ispis
8 5

U hrpu se mogu spremati i n-torke. Uspoređuju se po prvom elementu, kod jednakih po drugom, kao kod sortiranja u lekciji 24.

Program
import heapq
poslovi = []
heapq.heappush(poslovi, (-3, "zadaća"))
heapq.heappush(poslovi, (-5, "ispit"))
heapq.heappush(poslovi, (-1, "soba"))
while poslovi:
    hitnost, posao = heapq.heappop(poslovi)
    print(posao, -hitnost)
Ispis
ispit 5 zadaća 3 soba 1

3Pohlepno uz hrpu

Hrpa je najbolji prijatelj pohlepnih algoritama (lekcija 28): „uzmi trenutno najbolje” je upravo heappop. Primjer: treba spojiti N štapova u jedan; spajanje štapova duljina a i b košta a + b. Najjeftinije je uvijek spojiti dva najkraća.

Program
import heapq
h = [4, 3, 2, 6]
heapq.heapify(h)
cijena = 0
while len(h) > 1:
    a = heapq.heappop(h)
    b = heapq.heappop(h)
    cijena += a + b
    heapq.heappush(h, a + b)
print(cijena)
Ispis
29
Stani i razmisli

Zašto ovdje ne bi bilo dobro samo jednom sortirati štapove?

Pogledaj odgovor

Jer nakon spajanja nastaje novi štap koji treba umetnuti na pravo mjesto. Hrpa to radi brzo, a sortirana lista bi se morala stalno preslagivati.

4Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Što je sigurno na mjestu h[0] u hrpi?

Pitanje

Kako heapq-om dobiti najveći element?

Pitanje

Koliko otprilike koraka traje heappush za hrpu od N elemenata?

5Zadaci

Hitni poslovi

★☆☆ lagano

Naredba + x dodaje posao hitnosti x. Naredba ? uzima najhitniji posao (najveći x) i ispisuje njegovu hitnost. ? dolazi samo kad ima poslova.

Ulaz
U prvom retku M. Zatim M redaka s naredbama.
Izlaz
Za svaki ? jedan redak.
Ograničenja
1 ≤ M ≤ 100 000, 1 ≤ x ≤ 10⁹
Ulaz
5 + 3 + 9 ? + 4 ?
Izlaz
9 4
Treba ti pomoć?

heapq daje najmanji, pa u hrpu spremaj −x.

Riješi u evaluatoru

Štapovi

★★☆ srednje

Imamo N štapova. Spajanje dvaju štapova duljina a i b daje štap duljine a + b i košta a + b. Kolika je najmanja cijena spajanja svih štapova u jedan?

Ulaz
U prvom retku N. U drugom retku N duljina.
Izlaz
Najmanja cijena.
Ograničenja
1 ≤ N ≤ 100 000, 1 ≤ duljina ≤ 10⁹
Ulaz
4 4 3 2 6
Izlaz
29
Treba ti pomoć?

Pohlepno: uvijek spoji dva najkraća. Novi štap vrati u hrpu.

Riješi u evaluatoru

K-ti najveći

★★★ teže

Brojevi stižu jedan po jedan. Nakon svakog ispiši K-ti najveći od dosad stiglih brojeva, ili −1 ako ih je stiglo manje od K.

Ulaz
U prvom retku N i K. Zatim N redaka s po jednim brojem.
Izlaz
N redaka s odgovorima.
Ograničenja
1 ≤ K ≤ N ≤ 100 000, brojevi do 10⁹
Ulaz
5 2 4 9 1 7 8
Izlaz
-1 4 4 7 8
Treba ti pomoć?

Drži samo K najvećih brojeva u hrpi. Najmanji od njih (h[0]) je upravo K-ti najveći. Kad hrpa naraste preko K, izbaci najmanji.

Riješi u evaluatoru

6Što smo naučili

  • heapq.heappush dodaje, heapq.heappop vraća najmanji, h[0] ga samo gleda.
  • Za najveći spremaj negativne brojeve.
  • U hrpu mogu ići i n-torke: uspoređuju se po prvom elementu.
  • Pohlepni algoritmi i hrpa idu zajedno: „uzmi najbolje” je heappop.
Najčešće greške

ispisivanje hrpe kao da je sortirana · zaboravljen minus kod najvećeg · min() i remove() umjesto hrpe