როგორ მუშაობს heap sort?

Question

Accepted Answer

**Heap sort** აგებს **ორობითი heap**-ს მასივიდან, შემდეგ განმეორებით იღებს მაქსიმუმს დასალაგებელი თანმიმდევრობის წამოსახდებად. ის მუშაობს **O(n log n)** დროში და არის **in-place**.

## აზრი

Max-heap ინახავს ყველაზე დიდ ელემენტს root-ში. აირჩიე heap (O(n)), შემდეგ შეცვალე root ბოლოში, შეამცირე 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 queue**-ებს და top-k ელემენტების პოვნას.

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

Heap sort არის ერთადერთი საერთო სორტი, რომელიც არის worst-case O(n log n) და in-place, რაც მას ღირებულს ხდის მეხსიერებით შეზღუდულ ან გარანტირებული-შეკრულ პარამეტრებში.

ქვემოთ heap სტრუქტურა ფართოდ სასარგებლოა — priority queue-ები, დიჯკსტრას ალგორითმი, და streaming top-k.

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