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 heapq
uvozi 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.
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 = 0whilelen(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?
heapq drži najmanji na mjestu 0.
Pitanje
Kako heapq-om dobiti najveći element?
Najmanji negativni broj je najveći pravi broj.
Pitanje
Koliko otprilike koraka traje heappush za hrpu od N elemenata?
Dodavanje i uzimanje traju oko log N koraka.
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.