Heapify, push och pop från grunden
Implementera heapify-up för push och heapify-down för pop och bygg sedan en heap från en osorterad array i O(n) med Floyds algoritm.
Heapify, push och pop från grunden är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Bygga en MinHeap-klass
Att implementera en heap från grunden visar att ni behärskar den underliggande mekaniken och är något som ibland efterfrågas i intervjuer för seniora roller. En MinHeap-klass kapslar in en array och tillhandahåller operationerna push, pop, peek och size. Internt upprätthåller den heap-egenskapen genom att anropa sift-up efter push och sift-down efter pop. När ni förstår denna implementation blir Pythons heapq-modul helt begriplig.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Implementera sift-up
Sift-up jämför en nod med dess förälder och byter plats uppåt så länge heap-egenskapen (förälder <= barn för en min-heap) bryts. Det viktiga är att det nyligen insatta elementet finns sist och bubblar upp till sin rätta position. While-loopen körs högst floor(log n) gånger — trädets höjd. Tilldela i = parent i varje steg för att fortsätta förflyttningen uppåt.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapImplementera sift-down
Sift-down flyttar en nod nedåt genom att upprepade gånger byta plats med dess minsta barn (för en min-heap), tills inget barn är mindre eller noden når ett löv. Jämför alltid med båda barnen och byt plats med det mindre barnet för att bevara heap-egenskapen. Kom ihåg att kontrollera att barnens index ligger inom gränserna innan värdena jämförs.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkKomplettera MinHeap med pop
Pop-operationen tar bort och returnerar roten (minimum i en min-heap). För att bevara det kompletta binära trädets form flyttar ni det sista elementet till rotpositionen och utför sedan sift-down på det. På så sätt uppstår inga luckor i arrayen och representationen förblir giltig. Specialfall: om bara ett element återstår tas det bort och returneras direkt utan sift-down.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedFloyds heapify-algoritm
Floyds algoritm bygger en min-heap från en osorterad array på O(n) genom att anropa sift-down på varje nod som inte är ett löv, med början vid den sista inre noden (n//2 - 1) och vidare mot roten. Löv är redan giltiga enelementsheaps. O(n)-tidsgränsen beror på att de flesta noder finns nära trädets botten och bara behöver flyttas ned en kort sträcka.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Varför Floyds algoritm är O(n)
Beviset för O(n): trädet har n/2^(k+1) noder på höjd k. Varje nod på höjd k utför högst k byten under sift-down. Det totala arbetet = summan över alla höjder k: n/2^(k+1) * k. Denna geometriska serie konvergerar mot O(n). Jämför detta med naiv insättning ett element i taget: varje push tar O(log n), så n push-operationer kostar O(n log n). Floyds algoritm är strikt bättre vid konstruktion i ett enda parti.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Heap-push i en befintlig samling
Pythons heapq.heappushpop och heapq.heapreplace är effektiva kombinerade operationer. heappushpop(heap, item) lägger till det nya objektet och tar omedelbart bort det minsta — mer effektivt än två separata anrop. heapreplace(heap, item) tar bort det minsta och lägger till det nya objektet i ett enda steg (det nya objektet måste vara >= det gamla minimumvärdet för att det ska bli korrekt). Dessa operationer är användbara i strömningsalgoritmer för top-k.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternImplementera en MaxHeap från grunden
En MaxHeap vänder på jämförelsen: föräldern måste vara större än eller lika med alla efterkommande noder. Vänd helt enkelt på jämförelsen i sift-up och sift-down. Alternativt kan ni omsluta värden i en negationsklass eller negera heltal, som med Pythons heapq. Att implementera detta från grunden visar att min- och max-heaps är identiska strukturer där endast jämförelseoperatorn har ändrats.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Ta bort ett godtyckligt element från en heap
Att ta bort ett godtyckligt element (inte roten) från en heap tar O(log n), men kräver att elementets index är känt. Ersätt elementet med det sista elementet, ta bort det sista och utför sedan antingen sift-up eller sift-down på ersättningen (bara en riktning kommer att bryta mot heap-egenskapen). Denna teknik används i Dijkstras algoritm med lat borttagning och i prioritetsköer som stöder decrease-key-operationer.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validHeap i Top-K Frequent Elements
Top-K Frequent Elements (LeetCode #347) använder en min-heap med storlek k. Underhåll en min-heap där varje post är (frequency, element). Bearbeta varje unikt element: om heapen innehåller färre än k element lägger ni till det; annars tar ni bort heapens minimum och lägger till det nya elementet om dess frekvens överstiger minimumvärdets frekvens. Den slutliga heapen innehåller de k mest frekventa elementen på O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Heapar i schemaläggning
Utöver tävlingsprogrammering driver heapar verkliga schemaläggningssystem. Operativsystems uppgiftsschemaläggare använder en prioritetskö (heap) för att alltid köra den högst prioriterade process som är redo. Händelsestyrda simuleringar behandlar händelser i tidsordning med hjälp av en min-heap ordnad efter händelsetid. Schemaläggare för nätverkspaket prioriterar trafik efter tjänstekvalitetsklass. Att förstå heapen ger en mental modell för alla dessa system och kommer naturligt upp i systemdesignintervjuer om köhantering och schemaläggning.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderSnabbtest
Testa era kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen lärde ni er: MinHeap och MaxHeap från grunden med sift-up och sift-down, Floyds O(n)-algoritm för heapify och varför den är bättre än att lägga in element ett i taget med O(n log n), samt praktiska tillämpningar, däribland de k vanligaste elementen och delete-at-index. Härnäst utforskar vi Pythons heapq-modul och knep för max-heapar.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Heapify, push och pop från grunden” gratis?
Ja – hela texten till ”Heapify, push och pop från grunden” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Heapify, push och pop från grunden”?
Implementera heapify-up för push och heapify-down för pop och bygg sedan en heap från en osorterad array i O(n) med Floyds algoritm. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Heapify, push och pop från grunden”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Heap-egenskapen och arrayrepresentation
- Heapify, push och pop från grunden
- Pythons heapq och knep för max-heap
- Median från dataström och k-vägs-sammanfogning