Heap-uri și Cozi cu Priorități
Heap-uri și Cozi cu Priorități¶
Ce este un Heap?¶
Un heap binar este un arbore binar complet care respectă proprietatea de heap:
- Min-Heap: fiecare nod este $\leq$ copiii săi → rădăcina e elementul minim
- Max-Heap: fiecare nod este $\geq$ copiii săi → rădăcina e elementul maxim
De ce e important?¶
Un heap oferă acces la elementul minim/maxim în $O(1)$ și inserare/extragere în $O(\log n)$. Este structura de date ideală pentru cozi cu priorități — folosite în Dijkstra, planificarea proceselor, merge de fișiere, etc.
Reprezentare pe Array¶
Un heap se stochează eficient într-un array, fără pointeri:
- Rădăcina este la indexul
0 - Copilul stâng al nodului
i: $2i + 1$ - Copilul drept al nodului
i: $2i + 2$ - Părintele nodului
i: $\lfloor(i - 1) / 2\rfloor$
2 Array: [2, 5, 3, 8, 7, 6]
/ \
5 3 Index: 0 1 2 3 4 5
/ \ /
8 7 6
Implementare Min-Heap¶
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 _swap(self, i, j):
self.data[i], self.data[j] = self.data[j], self.data[i]
def peek(self):
"""Returnează minimul fără a-l extrage — O(1)"""
if not self.data:
raise IndexError("Heap gol")
return self.data[0]
def push(self, val):
"""Inserează un element — O(log n)"""
self.data.append(val)
self._sift_up(len(self.data) - 1)
def pop(self):
"""Extrage și returnează minimul — O(log n)"""
if not self.data:
raise IndexError("Heap gol")
# Punem ultimul element pe poziția rădăcinii
minimum = self.data[0]
self.data[0] = self.data[-1]
self.data.pop()
if self.data:
self._sift_down(0)
return minimum
def _sift_up(self, i):
"""Urcă elementul până respectă proprietatea de heap"""
while i > 0 and self.data[i] < self.data[self._parent(i)]:
self._swap(i, self._parent(i))
i = self._parent(i)
def _sift_down(self, i):
"""Coboară elementul până respectă proprietatea de heap"""
n = len(self.data)
while True:
smallest = i
l, r = self._left(i), self._right(i)
if l < n and self.data[l] < self.data[smallest]:
smallest = l
if r < n and self.data[r] < self.data[smallest]:
smallest = r
if smallest == i:
break
self._swap(i, smallest)
i = smallest
Vizualizarea operațiilor¶
Push(1) într-un min-heap [2, 5, 3, 8, 7]:
Pas 1: Adaugă la final Pas 2: Sift up
2 1
/ \ / \
5 3 → 5 2
/ \ / / \ /
8 7 1 8 7 3
1 este mai mic decât părintele (3), deci urcă. Apoi 1 < 2, deci urcă din nou la rădăcină.
Construirea unui Heap: $O(n)$, nu $O(n \log n)$!¶
Un rezultat surprinzător: putem construi un heap dintr-un array nesortrat în $O(n)$, nu $O(n \log n)$.
def build_heap(arr):
"""Construiește un min-heap in-place — O(n)"""
heap = MinHeap()
heap.data = arr[:]
# Sift down de la ultimul nod intern spre rădăcină
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heap._sift_down(i)
return heap
De ce $O(n)$? Nodurile de pe ultimul nivel (jumătate din noduri) nu necesită sift down. Nodurile de pe penultimul nivel fac cel mult 1 swap, etc. Suma totală:
$$\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} \cdot h = O(n)$$
Coada cu Priorități¶
O coadă cu priorități oferă două operații principale:
- insert(element, prioritate) — adaugă un element
- extract_min() (sau extract_max()) — scoate elementul cu prioritatea cea mai mare
Heap-ul este implementarea standard, dar putem compara:
| Implementare | insert | extract_min | peek |
|---|---|---|---|
| Array nesortat | $O(1)$ | $O(n)$ | $O(n)$ |
| Array sortat | $O(n)$ | $O(1)$ | $O(1)$ |
| Heap | $O(\log n)$ | $O(\log n)$ | $O(1)$ |
Python heapq¶
Python oferă modulul heapq care implementează un min-heap direct pe liste:
import heapq
# Creare heap din listă
data = [5, 3, 8, 1, 2]
heapq.heapify(data) # O(n) — in-place
print(data) # [1, 2, 8, 5, 3]
# Operații
heapq.heappush(data, 0) # inserare
smallest = heapq.heappop(data) # extragere min
# Top K elemente — O(n log k)
top_3 = heapq.nlargest(3, [4, 1, 7, 3, 8, 2]) # [8, 7, 4]
Aplicație: Merge K Sorted Lists¶
Dați $k$ liste sortate, interclasați-le într-o singură listă sortată.
def merge_k_sorted(lists):
"""
Interclasează k liste sortate folosind un min-heap.
Complexitate: O(N log k) unde N = total elemente
"""
heap = []
result = []
# Inițializăm heap-ul cu primul element din fiecare listă
for i, lst in enumerate(lists):
if lst:
# (valoare, index_lista, index_element)
heapq.heappush(heap, (lst[0], i, 0))
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# Dacă mai sunt elemente în lista respectivă
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return result
# Exemplu
lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lists)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
De ce $O(N \log k)$? Heap-ul conține mereu cel mult $k$ elemente (câte unul per listă). Fiecare din cele $N$ elemente este inserat și extras o singură dată.
Aplicație: Median Running (Flux de Date)¶
Găsirea medianei dintr-un flux continuu de numere:
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (jumătatea mică) — negăm valorile
self.hi = [] # min-heap (jumătatea mare)
def add(self, num):
heapq.heappush(self.lo, -num)
# Asigurăm că max(lo) <= min(hi)
if self.hi and (-self.lo[0] > self.hi[0]):
val = -heapq.heappop(self.lo)
heapq.heappush(self.hi, val)
# Echilibrăm dimensiunile (lo poate avea cel mult +1)
if len(self.lo) > len(self.hi) + 1:
val = -heapq.heappop(self.lo)
heapq.heappush(self.hi, val)
elif len(self.hi) > len(self.lo):
val = heapq.heappop(self.hi)
heapq.heappush(self.lo, -val)
def median(self):
if len(self.lo) > len(self.hi):
return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2
Idee: Folosim două heap-uri — un max-heap pentru jumătatea mică și un min-heap pentru jumătatea mare. Mediana este mereu accesibilă în $O(1)$, iar inserarea costă $O(\log n)$.
Exerciții¶
- Implementați un Max-Heap modificând Min-Heap-ul de mai sus
- Implementați Heap Sort in-place folosind un max-heap
- Dați $n$ puncte în plan, găsiți cele mai apropiate $k$ puncte de origine — ce complexitate puteți obține?
- Implementați operația
decrease_key(i, new_val)pe un min-heap. De ce este importantă pentru Dijkstra?