A binary heap minangka wit biner lengkap sing disimpen ing array sing njaga heap property: ing min-heap, saben parental kudu ≤ anak-anake, mula minimum tansah ana ing root. Iki nggawe dadi implementasi standar saka priority queue.
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
| Operation | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |
Heap menehi sampeyan item sing paling penting sabanjure kanthi langsung tanpa kudu njaga kabeh sing rapi sorte, sing luwih murah tinimbang nggawe ulang sorte.
Iki minangka tulang punggung algoritma sing dipandu prioritas lan piranti intervyu sing kerap kanggo pitakon "k paling gedhe/paling cilik".