Heapify, push i pop od podstaw
Zaimplementują Państwo heapify-up dla push i heapify-down dla pop, a następnie zbudują kopiec z nieposortowanej tablicy w O(n), korzystając z algorytmu Floyda.
Heapify, push i pop od podstaw to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Tworzenie klasy MinHeap
Implementacja kopca od podstaw pokazuje zrozumienie jego mechanizmów wewnętrznych i czasami jest wymagana podczas rozmów rekrutacyjnych na stanowiska seniorskie. Klasa MinHeap opakowuje tablicę i udostępnia operacje push, pop, peek oraz size. Wewnętrznie utrzymuje własność kopca, wywołując przesiewanie w górę po operacji push i przesiewanie w dół po operacji pop. Zrozumienie tej implementacji sprawia, że moduł Pythona heapq staje się całkowicie przejrzysty.
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')Implementowanie przesiewania w górę
Przesiewanie w górę porównuje węzeł z jego rodzicem i zamienia je miejscami w górę tak długo, jak długo naruszona jest własność kopca (rodzic <= dziecko w kopcu minimalnym). Kluczowe jest to, że nowo wstawiony element znajduje się na końcu i przesuwa się w górę do właściwego miejsca. Pętla while wykonuje się najwyżej floor(log n) razy — tyle wynosi wysokość drzewa. W każdym kroku należy przypisać i = parent, aby kontynuować przesuwanie w górę.
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-heapImplementowanie przesiewania w dół
Przesiewanie w dół przesuwa węzeł w dół, wielokrotnie zamieniając go z najmniejszym dzieckiem w przypadku kopca minimalnego, aż żadne dziecko nie będzie od niego mniejsze albo węzeł dotrze do liścia. Zawsze należy porównywać węzeł z obojgiem dzieci i zamieniać go z mniejszym z nich, aby zachować własność kopca. Przed porównaniem wartości należy sprawdzić, czy indeksy dzieci mieszczą się w granicach tablicy.
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 sinkUzupełnianie klasy MinHeap o operację pop
Operacja pop usuwa i zwraca korzeń, czyli minimum w kopcu minimalnym. Aby zachować kształt zupełnego drzewa binarnego, należy przenieść ostatni element na pozycję korzenia, a następnie przesunąć go w dół. Dzięki temu w tablicy nie powstają luki, a reprezentacja pozostaje poprawna. Przypadek brzegowy: jeśli pozostał tylko jeden element, należy usunąć go i zwrócić bez przesiewania w dół.
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] sortedAlgorytm kopcowania Floyda
Algorytm Floyda buduje kopiec minimalny z nieposortowanej tablicy w czasie O(n), wywołując przesiewanie w dół dla każdego węzła niebędącego liściem, zaczynając od ostatniego węzła wewnętrznego (n//2 - 1) i przesuwając się w kierunku korzenia. Liście są już poprawnymi, trywialnymi kopcami jednoelementowymi. Złożoność O(n) wynika z faktu, że większość węzłów znajduje się blisko dołu drzewa i musi przesunąć się w dół tylko na niewielką odległość.
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 1Dlaczego algorytm Floyda ma złożoność O(n)
Dowód złożoności O(n): drzewo ma n/2^(k+1) węzłów na wysokości k. Każdy węzeł na wysokości k wykonuje podczas przesiewania w dół najwyżej k zamian. Łączna praca = suma po wszystkich wysokościach k: n/2^(k+1) * k. Ten szereg geometryczny jest zbieżny do O(n). Dla porównania, naiwne wstawianie elementów pojedynczo ma koszt O(log n) dla każdej operacji push, więc n operacji push kosztuje O(n log n). Algorytm Floyda jest zdecydowanie lepszy przy budowaniu kopca partiami.
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')Wstawianie do istniejącej kolekcji kopca
Metody heapq.heappushpop i heapq.heapreplace języka Python to wydajne operacje łączone. heappushpop(heap, item) wstawia nowy element i natychmiast usuwa najmniejszy, dzięki czemu jest wydajniejsza niż dwa oddzielne wywołania. heapreplace(heap, item) usuwa najmniejszy element i wstawia nowy w jednym przebiegu (nowy element musi być >= starego minimum, aby operacja była poprawna). Operacje te są przydatne w strumieniowych algorytmach 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 patternImplementowanie klasy MaxHeap od podstaw
MaxHeap odwraca kierunek porównywania: rodzic musi być większy lub równy wszystkim swoim potomkom. Wystarczy odwrócić porównanie w przesiewaniu w górę i w dół. Alternatywnie można opakować wartości w klasę wykonującą negację albo negować liczby całkowite, tak jak robi się to w przypadku modułu heapq języka Python. Implementacja od podstaw pokazuje, że kopce minimalne i maksymalne mają identyczną strukturę, a różni je tylko operator porównania.
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]Usuwanie dowolnego elementu z kopca
Usunięcie dowolnego elementu, który nie jest korzeniem, z kopca ma złożoność O(log n), ale wymaga znajomości indeksu tego elementu. Element należy zastąpić ostatnim elementem, usunąć ostatni element, a następnie przesunąć element zastępujący w górę albo w dół — tylko jeden z tych kierunków może naruszać własność kopca. Technika ta jest używana w algorytmie Dijkstry z leniwym usuwaniem oraz w kolejkach priorytetowych obsługujących operacje decrease-key.
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 validKopiec w problemie Top-K Frequent Elements
Top-K Frequent Elements (LeetCode nr 347) wykorzystuje kopiec minimalny o rozmiarze k. Należy utrzymywać kopiec minimalny, w którym każdy wpis ma postać (frequency, element). Dla każdego unikatowego elementu: jeśli kopiec zawiera mniej niż k elementów, należy go wstawić; w przeciwnym razie, jeśli częstość nowego elementu przekracza minimum w kopcu, należy usunąć minimum i wstawić nowy element. Końcowy kopiec zawiera k najczęściej występujących elementów, a złożoność czasowa wynosi 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]Zastosowania kopców w planowaniu zadań
Poza programowaniem konkursowym kopce są podstawą rzeczywistych systemów planowania zadań. Harmonogramy zadań systemów operacyjnych używają kolejki priorytetowej (kopca), aby zawsze uruchamiać gotowy proces o najwyższym priorytecie. Symulacje sterowane zdarzeniami przetwarzają zdarzenia w kolejności czasowej, używając kopca minimum uporządkowanego według czasu zdarzenia. Harmonogramy pakietów sieciowych nadają priorytety ruchowi na podstawie klasy jakości usług. Zrozumienie działania kopca daje Państwu model mentalny wszystkich tych systemów i naturalnie pojawia się podczas rozmów kwalifikacyjnych dotyczących projektowania systemów, kolejkowania i planowania zadań.
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 orderSzybkie sprawdzenie
Proszę sprawdzić swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: MinHeap i MaxHeap od podstaw z operacjami sift-up i sift-down, algorytm heapify Floyda o złożoności O(n) oraz przyczynę, dla której jest on wydajniejszy niż pojedyncze wstawianie o złożoności O(n log n), a także praktyczne zastosowania, w tym najczęściej występujące elementy top-k i usuwanie po indeksie. W następnej części poznają Państwo moduł heapq języka Python oraz sposoby symulowania kopca maksymalnego.
Często zadawane pytania
Czy lekcja „Heapify, push i pop od podstaw” jest bezpłatna?
Tak — pełny tekst „Heapify, push i pop od podstaw” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Heapify, push i pop od podstaw”?
Zaimplementują Państwo heapify-up dla push i heapify-down dla pop, a następnie zbudują kopiec z nieposortowanej tablicy w O(n), korzystając z algorytmu Floyda. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Heapify, push i pop od podstaw”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Własność kopca i reprezentacja tablicowa
- Heapify, push i pop od podstaw
- heapq w Pythonie i sztuczki z kopcem maksymalnym
- Mediana ze strumienia danych i scalanie k-way