Pythonin heapq ja max-heap-temput
Käyttäkää heapq.heappush- ja heapq.heappop-funktioita, simuloikaa max-heap negaamalla arvot ja soveltakaa heapq.nlargest- ja heapq.nsmallest-funktioita nopeisiin top-k-kyselyihin.
Pythonin heapq ja max-heap-temput on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Pythonin heapq-moduulin yleiskatsaus
Pythonin heapq-moduuli tarjoaa tavallisen Python-listan päälle toteutetun minimikeon. Toisin kuin erillinen kekoluokka, heapq toimii olemassa olevilla listoilla suoraan niiden sisältöä muokaten. Moduulin funktiot ovat seuraavat: heapify rakentaa keon O(n)-ajassa, heappush lisää alkion O(log n) -ajassa, heappop poistaa pienimmän alkion O(log n) -ajassa, ja heappushpop / heapreplace tehostavat yhdistettyjä operaatioita.
import heapq
# heapq operates on plain Python lists
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print('Heap array:', heap) # internal array (not sorted!)
print('Peek min:', heap[0]) # O(1) min access
print('Pop min:', heapq.heappop(heap)) # 1
print('Next min:', heap[0]) # 2
# heapify: turn any list into a heap in O(n)
data = [9, 4, 7, 1, 3, 6, 2]
heapq.heapify(data)
print('Heapified:', data, '| min:', data[0])Maksimikeko arvojen vastalukuja käyttämällä
Pythonin heapq tarjoaa vain minimikeon. Maksimikekoa simuloidaan muuttamalla kaikki arvot vastaluvuiksi ennen niiden lisäämistä ja muuttamalla ne uudelleen vastaluvuiksi poiminnan jälkeen. Tämä toimii, koska keko järjestää alkiot tallennettujen arvojen perusteella ja vastaluvuksi muuttaminen kääntää järjestyksen. Molemmissa vaiheissa on toimittava samalla tavalla: arvo muutetaan vastaluvuksi ennen lisäämistä ja uudelleen poiminnan jälkeen. Jommankumman vaiheen unohtaminen on yleinen virhe haastattelutehtävissä.
import heapq
max_heap = []
for val in [5, 1, 8, 3, 9, 2]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap internal:', max_heap) # all negated
# Pop in descending order:
results = []
while max_heap:
results.append(-heapq.heappop(max_heap)) # negate on pop
print('Sorted descending:', results) # [9, 8, 5, 3, 2, 1]
# Common pattern: top-k largest
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
heap = []
for x in data:
heapq.heappush(heap, -x)
print('Top', k, ':', [-heapq.heappop(heap) for _ in range(k)])heapq.nlargest ja nsmallest
heapq.nlargest(k, iterable) ja heapq.nsmallest(k, iterable) palauttavat k suurinta tai pienintä alkiota. Niiden aikavaativuus on O(n log k), joten ne ovat tehokkaampia kuin koko aineiston järjestäminen (O(n log n)), kun k on paljon pienempi kuin n. Sisäisesti ne käyttävät kooltaan k:n kokoista kekoa. Kun k on lähellä n:ää, Python siirtyy käyttämään koko aineiston järjestämistä. Näitä funktioita kannattaa käyttää kertaluonteisiin top-k-kyselyihin ilman ylläpidettävää pysyvää kekoa.
import heapq
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 7]
# Top 3 largest:
print(heapq.nlargest(3, data)) # [9, 8, 7]
# Top 3 smallest:
print(heapq.nsmallest(3, data)) # [1, 1, 2]
# With a key function:
words = ['banana', 'apple', 'cherry', 'date', 'elderberry']
print(heapq.nlargest(2, words, key=len)) # ['elderberry', 'banana']
print(heapq.nsmallest(2, words, key=len)) # ['date', 'apple']
# Note: when k ~ n, use sorted() instead:
# sorted(data)[-k:] or sorted(data, reverse=True)[:k]Keko monikoilla ja monimutkaisilla vertailuavaimilla
Kun kekoon tallennettaville alkioille tarvitaan mukautettu vertailuavain, ne kannattaa tallentaa monikkoina (priority, data). Pythonin heapq vertailee monikoita alkio kerrallaan, joten ensin verrataan prioriteetteja. Jos prioriteetit ovat samat, verrataan toista alkiota, mikä voi aiheuttaa virheitä, jos data ei ole vertailukelpoista. Turvallisinta on lisätä tasa-arvoisten prioriteettien ratkaisemiseksi yksilöllinen laskuri, jotta data-alkioita ei koskaan tarvitse vertailla suoraan.
import heapq
import itertools
# Pattern: (priority, counter, item)
# Counter ensures unique tiebreaker, avoids comparing items
counter = itertools.count()
heap = []
def push_task(priority, task):
heapq.heappush(heap, (priority, next(counter), task))
push_task(3, 'low priority task')
push_task(1, 'high priority task')
push_task(2, 'medium priority task')
push_task(1, 'another high priority')
while heap:
pri, cnt, task = heapq.heappop(heap)
print(f'P{pri}: {task}')
# Output in priority order: P1, P1, P2, P3heapq.merge: järjestettyjen iteroitavien kohteiden yhdistäminen
heapq.merge(*iterables) yhdistää laiskasti useita järjestettyjä iteroitavia kohteita yhdeksi järjestetyksi tulosteeksi lataamatta kaikkea dataa muistiin. Tämä vastaa k-suuntaista yhdistämistä, jossa käytetään kooltaan k:n kokoista minimikekoa, ja sitä hyödynnetään ulkoisen järjestämisen algoritmeissa. Funktio palauttaa iteraattorin, joten alkiot tuotetaan yksi kerrallaan. Tämä sopii erinomaisesti suurille aineistoille ja suoratoistotilanteisiin.
import heapq
# Merge multiple sorted lists efficiently
sorted_lists = [
[1, 5, 9],
[2, 6, 8],
[3, 4, 7]
]
# heapq.merge takes sorted iterables and returns a merged sorted iterator
merged = list(heapq.merge(*sorted_lists))
print('Merged:', merged) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
# The k-way merge manually (educational version):
def merge_k_sorted(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
heapq.heappush(heap, (lists[list_idx][elem_idx+1], list_idx, elem_idx+1))
return result
print('Manual k-way:', merge_k_sorted(sorted_lists))Laiskan poiston malli kekorakenteissa
Kun keosta on poistettava mielivaltaisia alkioita mutta niiden indeksiä ei tiedetä, voidaan käyttää laiskaa poistoa: alkiot merkitään poistetuksi erilliseen joukkoon ja ohitetaan niitä poimittaessa. Aikavaativuus on amortisoidusti O(log n), eikä indeksien seuraamisen monimutkaisuutta tarvita. Tämä on vakiintunut lähestymistapa Dijkstran algoritmissa duplikaattimerkintöjen kanssa sekä tehtävien ajoituksen simulaatioissa.
import heapq
class LazyHeap:
def __init__(self):
self._heap = []
self._removed = set()
def push(self, task):
heapq.heappush(self._heap, task)
def remove(self, task):
self._removed.add(task) # mark as removed
def pop(self):
while self._heap:
task = heapq.heappop(self._heap)
if task not in self._removed:
return task
return None
lh = LazyHeap()
for t in [5, 1, 8, 3, 2]:
lh.push(t)
lh.remove(1) # 'delete' 1 lazily
lh.remove(8) # 'delete' 8 lazily
results = [lh.pop() for _ in range(3)]
print(results) # [2, 3, 5] -- 1 and 8 skippedTietovirran k:nneksi suurin alkio
Tietovirran k:nneksi suurin alkio (LeetCode #703) ratkaistaan ylläpitämällä kooltaan k:n kokoista minimikekoa. Keon juuressa on aina tähän mennessä nähty k:nneksi suurin alkio. Kun uusi luku saapuu, se lisätään kekoon, ja jos keon koko ylittää k:n, pienin alkio poimitaan. Juuri on aina k:nneksi suurin, koska keossa on täsmälleen k-1 sitä suurempaa alkiota.
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for num in nums:
self.add(num)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # remove smallest
return self.heap[0] # kth largest = root of min-heap
# k=3, initial=[4,5,8,2]
kl = KthLargest(3, [4, 5, 8, 2])
print(kl.add(3)) # 4 (top 3: 8,5,4 -- kth=4)
print(kl.add(5)) # 5 (top 3: 8,5,5 -- kth=5)
print(kl.add(10)) # 5 (top 3: 10,8,5 -- kth=5)
print(kl.add(9)) # 8 (top 3: 10,9,8 -- kth=8)K pienimmän summan parin etsiminen
K pienimmän summan paria (LeetCode #373) etsitään minimikeon avulla järjestyksessä. Aluksi kekoon lisätään kaikki parit (nums1[0], nums2[j]) jokaiselle j:n arvolle. Pienin pari poimitaan, ja parille (nums1[i], nums2[j]) lisätään tämän jälkeen (nums1[i+1], nums2[j]), joka on saman nums2-sarakkeen seuraava ehdokas. Tämä on yleinen malli järjestettyjen pari- tai tuoteyhdistelmien tuottamiseen kekorakenteen avulla.
import heapq
def k_smallest_pairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
heap = []
# Initialize with pairs (nums1[0], nums2[j])
for j in range(min(k, len(nums2))):
heapq.heappush(heap, (nums1[0] + nums2[j], 0, j))
result = []
while heap and len(result) < k:
total, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])
if i + 1 < len(nums1):
heapq.heappush(heap, (nums1[i+1] + nums2[j], i+1, j))
return result
print(k_smallest_pairs([1,7,11], [2,4,6], 3))
# [[1,2], [1,4], [1,6]]Tehtävien ajoittaminen maksimikeolla
Tehtävien ajoittaja (LeetCode #621) -tehtävässä etsitään lyhintä aikaa n tehtävän ajoittamiseen, kun saman tehtävän suoritusten välillä on n aikavälin pituinen jäähdytysjakso. Tehtävien esiintymismääristä muodostetaan maksimikeko: kullakin ajanhetkellä valitaan useimmin esiintyvä käytettävissä oleva tehtävä, vähennetään sen määrää ja siirretään se jäähdytykseen. Kussakin jaksossa käsitellään k=n+1 tehtävää tai jakso täytetään joutoajalla. Tämä maksimikekoon perustuva ahne lähestymistapa tuottaa optimaalisen vastauksen.
import heapq
from collections import Counter
def least_interval(tasks, n):
freq = Counter(tasks)
heap = [-f for f in freq.values()] # max-heap (negated)
heapq.heapify(heap)
time = 0
while heap:
cycle = n + 1
temp = []
for _ in range(cycle):
if heap:
temp.append(heapq.heappop(heap))
for f in temp:
if f + 1 < 0: # still tasks remaining
heapq.heappush(heap, f + 1)
# Add full cycle or remaining tasks if queue empty
time += cycle if heap else len(temp)
return time
print(least_interval(['A','A','A','B','B','B'], 2)) # 8
print(least_interval(['A','A','A','B','B','B'], 0)) # 6Keko Dijkstran algoritmissa
Dijkstran algoritmin prioriteettijono toteutetaan minimikeolla. Tallennetaan monikkoja (distance, node) ja käsitellään aina ensin lähin vierailematon solmu. Jos poimitun solmun etäisyys on suurempi kuin sille tällä hetkellä tunnettu lyhin etäisyys eli kyseessä on laiskan poiston vanhentunut merkintä, se ohitetaan. Näin vältetään decrease-key-operaation tarve ja toteutus pysyy yksinkertaisena, samalla kun aikavaativuus säilyy muodossa O((V + E) log V).
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # stale entry, skip
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = {
'A': [('B', 4), ('C', 1)],
'B': [('D', 1)],
'C': [('B', 2), ('D', 5)],
'D': []
}
print(dijkstra(graph, 'A')) # {'A':0,'B':3,'C':1,'D':4}Merkkijonon järjestäminen uudelleen maksimikeolla
Merkkijonon järjestäminen uudelleen (LeetCode #767) -tehtävässä merkkijono on järjestettävä uudelleen siten, ettei kaksi vierekkäistä merkkiä ole samoja. Käytetään monikoista (-frequency, char) muodostettua maksimikekoa. Kussakin vaiheessa poimitaan useimmin esiintyvä merkki. Jos edellinen merkki on sama kuin useimmin esiintyvä merkki, poimitaan toiseksi useimmin esiintyvä merkki. Tämä ahne lähestymistapa varmistaa, että eniten rajoitteita aiheuttava merkki sijoitetaan mahdollisimman aikaisin.
import heapq
from collections import Counter
def reorganize_string(s):
freq = Counter(s)
heap = [(-f, c) for c, f in freq.items()]
heapq.heapify(heap)
result = []
prev_freq, prev_char = 0, ''
while heap:
freq, char = heapq.heappop(heap)
result.append(char)
# Push back the previous character if still remaining
if prev_freq < 0:
heapq.heappush(heap, (prev_freq, prev_char))
prev_freq, prev_char = freq + 1, char # decrement freq (less negative)
result_str = ''.join(result)
# Verify no adjacent duplicates
return result_str if len(result_str) == len(s) else ''
print(reorganize_string('aab')) # 'aba'
print(reorganize_string('aaab')) # '' (impossible)Pikatesti
Tässä testataan ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheista.
Oppitunnin kertaus
Tässä oppitunnissa opitte Pythonin heapq-moduulin ohjelmointirajapinnan, johon kuuluvat heapify, heappush, heappop, nlargest, nsmallest ja merge, maksimikekosimulaation arvojen vastalukuja käyttämällä sekä yleisiä kekorakenteisiin liittyviä haastattelutehtävämalleja, kuten top-k-suoratoisto, tietovirran k:nneksi suurin alkio, tehtävien ajoittaminen ja Dijkstra. Seuraavaksi käsitellään tietovirran mediaania ja k-suuntaista yhdistämistä.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Pythonin heapq ja max-heap-temput” ilmainen?
Kyllä – oppitunnin ”Pythonin heapq ja max-heap-temput” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Pythonin heapq ja max-heap-temput”?
Käyttäkää heapq.heappush- ja heapq.heappop-funktioita, simuloikaa max-heap negaamalla arvot ja soveltakaa heapq.nlargest- ja heapq.nsmallest-funktioita nopeisiin top-k-kyselyihin. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Pythonin heapq ja max-heap-temput”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Keon ominaisuus ja taulukkoesitys
- Heapify, push ja pop alusta alkaen
- Pythonin heapq ja max-heap-temput
- Mediaani tietovirrasta ja k-suuntainen yhdistäminen