Πώς λειτουργεί το heap sort;

Question

Accepted Answer

**Το Heap Sort** κατασκευάζει ένα **δυαδικό heap** από τον πίνακα, και στη συνέχεια εξάγει επανειλημμένως το μέγιστο για να παράγει ταξινομημένη σειρά. Εκτελείται σε **O(n log n)** και είναι **in-place**.

## Η ιδέα

Ένα max-heap κρατά το μεγαλύτερο στοιχείο στη ρίζα. Κατασκευάστε το heap (O(n)), στη συνέχεια ανταλλάξτε τη ρίζα στο τέλος, συρρικνώστε το heap, και ξανακάνετε heapify (sift down) — n φορές.

## Παράδειγμα

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

Μια κλασική υλοποίηση το κάνει in-place με sift down μέσα στον πίνακα.

## Πολυπλοκότητα

- **Χρόνος:** O(n log n) σε όλες τις περιπτώσεις. **Χώρος:** O(1) in-place.

## Πότε να χρησιμοποιήσετε / Παγίδες

Χρησιμοποιήστε όταν χρειάζεστε **εγγυημένο O(n log n)** *και* **O(1) επιπλέον μνήμη** (merge sort χρειάζεται O(n); quicksort κινδυνεύει με O(n²)). Δεν είναι **σταθερό** και έχει κακή cache locality, οπότε συχνά είναι πιο αργό στην πράξη από το quicksort. Το ίδιο heap τροφοδοτεί **priority queues** και εύρεση top-k στοιχείων.

## Γιατί έχει σημασία

Το Heap Sort είναι η μόνη κοινή ταξινόμηση που είναι ταυτόχρονα worst-case O(n log n) και in-place, καθιστώντας την πολύτιμη σε ρυθμίσεις περιορισμένης μνήμης ή εγγυημένων ορίων.

Η δομή heap από κάτω είναι ευρέως χρήσιμη — priority queues, αλγόριθμος Dijkstra, και streaming top-k.

Παγιώνει την ιδέα ότι η σωστή δομή δεδομένων κάνει έναν αλγόριθμο αποτελεσματικό.