Heap sort ทำงานอย่างไร

Question

IT Interview Practice · Accepted Answer

**Heap sort** สร้าง **binary heap** จากอาร์เรย์ จากนั้นดึงค่าสูงสุดออกมาซ้ำๆ เพื่อสร้างลำดับที่เรียงลำดับ ทำงานใน **O(n log n)** และ **ในที่**

## แนวคิด

Max-heap รักษาองค์ประกอบที่ใหญ่ที่สุดไว้ที่ราก สร้าง heap (O(n)) จากนั้นสลับรากไปยังส่วนท้าย ย่อขนาด heap และ re-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]
```

การใช้งานแบบคลาสสิคทำสิ่งนี้ในที่โดยการ sift down ภายในอาร์เรย์

## ความซับซ้อน

- **เวลา:** O(n log n) ในทุกกรณี **พื้นที่:** O(1) ในที่

## เมื่อใดควรใช้ / ข้อเสีย

ใช้เมื่อคุณต้องการ **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's algorithm และ streaming top-k

มันปูคอนกรีตแนวคิดที่ว่าโครงสร้างข้อมูลที่ถูกต้องทำให้อัลกอริทึมมีประสิทธิภาพ

แนวคิด

ตัวอย่าง

ความซับซ้อน

เมื่อใดควรใช้ / ข้อเสีย

เพราะเหตุใดจึงสำคัญ

คำถามที่เกี่ยวข้อง