Un binary heap este un arbore binar complet stocat într-un array care menține proprietatea heap: într-un min-heap, fiecare părinte este ≤ copiilor săi, deci minimul se află întotdeauna la rădăcină. Aceasta îl face implementarea standard a unei cozi de prioritate.
1 index: 0 1 2 3 4
/ \ array: [1, 3, 5, 8, 4]
3 5 parent(i) = (i-1)//2
/ \ left(i) = 2i+1
8 4 right(i) = 2i+2
import heapq
h = []
heapq.heappush(h, 5) # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # peek min -> O(1)
heapq.heappop(h) # O(log n) — remove root, sift down -> 1
| Operație | Timp |
|---|---|
| peek min/max | O(1) |
| push (inserare) | O(log n) |
| pop (extragere) | O(log n) |
| construire heap din n elemente | O(n) |
Un heap îți oferă următorul element cel mai important instantaneu, fără a menține totul complet sortat, ceea ce este mult mai ieftin decât re-sortarea.
Este coloana vertebrală a algoritmilor condui de prioritate și un instrument frecvent în interviuri pentru întrebări de tip "k cel mai mare/mic".
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează