Heap sort, diziden bir binary heap oluşturur, ardından sıralanmış sıra üretmek için en büyük öğeyi tekrar tekrar çıkarır. O(n log n) içinde çalışır ve yerinde dir.
Bir max-heap en büyük öğeyi kökte tutar. Heap oluşturun (O(n)), kökü sona değiştirin, heap i küçültün ve yeniden heapify edin (sift down) — n kez.
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]
Klasik bir uygulama bunu dizi içinde sift down yaparak yerinde yapar.
Garantili O(n log n) ve O(1) ekstra bellek gerektiğinde kullanın (merge sort O(n) gerektirir; quicksort O(n²) riski taşır). Stabil değildir ve zayıf cache lokalitesine sahiptir, bu nedenle pratikte quicksort tan genellikle daha yavaştır. Aynı heap, öncelik kuyrukları ve top-k öğelerini bulma işlevini sağlar.
Heap sort, hem en kötü durumda O(n log n) hem de yerinde olan tek ortak sıralamadır; bu da bellek kısıtlı veya garantili sınır ayarlarında değerli hale getirir.
Heap yapısı yaygın şekilde faydalıdır — öncelik kuyrukları, Dijkstra algoritması ve streaming top-k.
Doğru veri yapısının bir algoritmayı verimli hale getirdiği fikrini pekiştirir.
Junior'dan Senior'a detaylı cevaplarla bir BT mülakat soruları kütüphanesi.
Bağış Yap