Heap sort xây dựng một binary heap từ mảng, rồi liên tục trích xuất giá trị lớn nhất để tạo ra thứ tự đã sắp xếp. Nó chạy trong O(n log n) và tại chỗ (in-place).
Ý tưởng
Một max-heap giữ phần tử lớn nhất ở gốc. Xây dựng heap (O(n)), rồi hoán đổi gốc xuống cuối, thu nhỏ heap, và tái lập heap (sift down) — n lần.
Ví dụ
heapq
():
heapq.heapify(arr)
[heapq.heappop(arr)
_ ((arr))]
heap_sort([, , , , ])
