Kaip veikia šakos rūšiavimas (heap sort)?

Question

Accepted Answer

**Šakos rūšiavimas** iš masyvo sukuria **dvejetainę šaką**, o tada pakartotinai išimami didžiausi elementai, kad būtų gauta surūšiuota tvarka. Jis vykdomas **O(n log n)** laiku ir yra **in-place**.

## Idėja

Max-šaka laiko didžiausią elementą šaknies vietoje. Sukurkite šaką (O(n)), tada sukeiskite šaknį galu, sumažinkite šaką ir vėl nuheapify (sift down) — n kartų.

## Pavyzdys

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

Klasikinis įgyvendinimas tai atlieka in-place, atliekant sift down masyve.

## Sudėtingumas

- **Laikas:** O(n log n) visais atvejais. **Vieta:** O(1) in-place.

## Kada naudoti / spąstai

Naudokite, kai reikia **garantuoto O(n log n)** *ir* **O(1) papildomos atminties** (merge sort reikalinga O(n); quicksort rizikuoja O(n²)). Tai **nėra stabilu** ir turi prastą cache lokalybę, todėl praktikoje dažnai buvimas lėtesnis nei quicksort. Tą pačią šaką valdo **priority queue** ir topinimo k elementų paieška.

## Kodėl tai svarbu

Šakos rūšiavimas yra vienintelis bendras rūšiavimas, kuris yra ir worst-case O(n log n), ir in-place, dėl kurio jis brangus atminčiu apribotuose arba garantuoto susijungimo nustatymuose.

Po to esanti šakos struktūra plačiai naudinga — priority queue, Dijkstros algoritmas ir streaming top-k.

Tai sustiprina idėją, kad teisinga duomenų struktūra algoritmo efektyvumą.