Heap sort membina binary heap daripada array, kemudian secara berulang mengekstrak maksimum untuk menghasilkan susunan yang disusun. Ia berjalan dalam O(n log n) dan in-place.
Max-heap menyimpan elemen terbesar di akar. Bina heap (O(n)), kemudian tukarkan akar ke hujung, susutkan heap, dan padu-semulakan (sift down) — n kali.
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 melakukannya in-place dengan sift down dalam array.
Gunakan apabila anda memerlukan O(n log n) terjamin dan memori tambahan O(1) (merge sort memerlukan O(n); quicksort berisiko O(n²)). Ia tidak stabil dan mempunyai lokaliti cache yang buruk, jadi sering lebih perlahan dalam amalan berbanding quicksort. Heap yang sama menjadi kekuatan barisan keutamaan dan mencari elemen top-k.
Heap sort adalah satu-satunya jenis sort biasa yang merupakan kes terburuk O(n log n) dan in-place, menjadikannya berharga dalam tetapan terbatas memori atau batas terjamin.
Struktur heap di bawah adalah berguna secara meluas — barisan keutamaan, algoritma Dijkstra, dan streaming top-k.
Ia mengukuhkan idea bahawa struktur data yang betul membuat algoritma cekap.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma