Build heap ve sırala
- Algoritmalar kursu
- Orta seviye
- Ders 11/80
- 4 dk
Diziden yığın kurup teker teker çıkararak sıralamayı öğrenirsin.
Build heap ve sırala
Heap sort iki aşamada çalışır. Önce diziyi max-heap yaparız: yaprak olmayan son düğümden köke kadar her i için heapify(arr, n, i) çağrılır. Bu O(n).
Sonra kök (en büyük) son elemanla takas edilir, heap boyutu bir azalır ve kök için heapify çağrılır. Bu n-1 kez tekrarlanır; her biri O(log n).
Toplam: O(n log n). Yerinde çalışır, kararlı değildir.
Kökü sona taşı
Max-heap kurulduğunda kök arr[0] en büyük elemandır. Onu arr[n-1] ile takas ederiz; en büyük eleman doğru yerine yerleşir.
Sonra heap boyutu n-1'e düşürülür ve kök heapify edilir. Bu, ikinci en büyüğü tepeye çıkarır. Tekrar tekrar.
Her takas + heapify, bir elemanı yerine koyar. n adımda dizi sıralanır.
Uygulama Heap sort
heap_sort(arr) yaz. Önce max-heap kur, sonra kökü sona taşıyıp heapify et. arr=[5,2,8,1,9]; heap_sort(arr); print(arr) ile [1, 2, 5, 8, 9] yazdır.
Başlangıç kodu
def heap_sort(arr):
# Build heap ve sıralaÖrnek çözüm
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
# Build heap ve sırala
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
arr = [5, 2, 8, 1, 9]
heap_sort(arr)
print(arr)Beklenen çıktı
[1, 2, 5, 8, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Build heap ve sırala: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Build heap |
O(n) |
Sıralama |
O(n log n) |
Bellek |
O(1) ek |
Kararlı |
Hayır |
2 Build heap kaç iş yapar?
- O(1)
- O(n^2)
- O(log n)
- O(n) Doğru cevap
Açıklama: O(n)
3 Takas hedefi
arr[0], arr[i] = arr[i], ____arr[0], arr[i] = arr[i], arr[0]Açıklama: arr[0] doğru.