Piye cara heap sort makarya?

Question

IT Interview Practice · Accepted Answer

**Heap sort** nggawe **binary heap** saka array, banjur mbukak-mbukak nyuplek maksimum kanggo ngasilake urutan sing wis disortir. Tumakak ing **O(n log n)** lan **in-place**.

## Gagasan

Max-heap nyimpan elemen paling gedhe ing akar. Bangun heap (O(n)), banjur tabletake akar menyang mburi, ngecilake heap, lan mbalekke-heapify (sift down) — n kali.

## Conto

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

Implementasi klasik nindakake ing place kanthi sift down ing array.

## Kompleksitas

- **Wektu:** O(n log n) ing kabeh kasus. **Ruang:** O(1) in-place.

## Kapan nggunakna / pitfalls

Gunakna nalika butuh **O(n log n) garantis** *lan* **O(1) memori tambahan** (merge sort perlu O(n); quicksort dudu O(n²)). **Ora stabil** lan dudu cache locality apik, dadi asring luwih alon ing praktik tinimbang quicksort. Heap sing padha nyaupot **priority queue** lan nggoleki elemen top-k.

## Mengapa iku penting

Heap sort minangka siji-satune sortir umum sing worst-case O(n log n) lan in-place, nggawe iku berharga ing setelan memory-constrained utawa guaranteed-bound.

Struktuur heap ing ngisor minangka luwih migunani — priority queue, algoritma Dijkstra, lan streaming top-k.

Umum-umum ide yen struktur data sing bener nggawe algoritma efisien.

Gagasan

Conto

Kompleksitas

Kapan nggunakna / pitfalls

Mengapa iku penting

Pitakon sing gegandhengan