Kako deluje razvrščanje s kopico (heap sort)?

Question

Accepted Answer

**Heap sort** gradi **binarno kopico** iz polja, nato pa večkrat ekstrahira maksimum, da proizvede sortirano zaporedje. Teče v **O(n log n)** in je **na mestu**.

## Ideja

Max-kopica drži največji element v korenu. Zgradite kopico (O(n)), nato zamenjajte koren na konec, zmanjšajte kopico in ponovno heapificirajte (sift down) — n-krat.

## Primer

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Klasična implementacija to naredi na mestu z sifting down znotraj polja.

## Časovna zahtevnost

- **Čas:** O(n log n) v vseh primerih. **Prostor:** O(1) na mestu.

## Kdaj uporabiti / pasti

Uporabite, ko potrebujete **garantirano O(n log n)** *in* **O(1) dodatni pomnilnik** (merge sort potrebuje O(n); quicksort tvega O(n²)). **Ni stabilna** in ima slabo lokalnost predpomnilnika, zato je v praksi pogosto počasnejša od quicksorta. Ista kopica poganja **prioritetne vrste** in iskanje top-k elementov.

## Zakaj je to pomembno

Heap sort je edina pogosta vrsta sortiranja, ki je hkrati v najslabšem primeru O(n log n) in na mestu, kar ga naredi dragoceno v nastavitvah s omejenimi pomnilniki ali garantiranimi mejami.

Struktura kopice je osnovna — prioritetne vrste, Dijkstrin algoritem in streaming top-k.

Utrjuje idejo, da prava podatkovna struktura naredi algoritem učinkovit.