რა არის heap და როგორ იყენებს ის priority queue-ს?

Question

Accepted Answer

**binary heap** არის სრული ორობითი ხე, რომელიც ინახება მასივში და ინარჩუნებს **heap property**-ს: **min-heap**-ში, ყოველი მშობელი ≤ თავისი შვილებია, ამიტომ **მინიმუმი ყოველთვის ფესვში არის**. ეს მას **priority queue**-ის სტანდარტული განხორციელება ხდის.

## Array layout

```text
       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
```

## Operations

```python
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
```

## Complexity

| Operation | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |

## When to use

- **Scheduling** by priority (e.g. OS task schedulers).
- **Dijkstra / Prim** shortest-path and MST algorithms.
- **Top-K** problems and streaming medians.
- **Heap sort** (in-place O(n log n)).

## რატომ არის მნიშვნელოვანი

Heap გიქმნით მომდევნო ყველაზე მნიშვნელოვან ელემენტს მაშინვე ყველაფრის სრულად დახარისხების გარეშე, რაც ხელახლა დახარისხებაზე გაცილებით იაფია.

ეს არის პრიორიტეტის მიერ ამოძრავებული ალგორითმების საფუძველი და ხშირი ინტერვიუს ხელსაწყო "k ყველაზე დიდი/მცირე" კითხვებისთვის.

Operation	Time
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap from n items	O(n)