Heapify
- Algoritmalar kursu
- Orta seviye
- Ders 10/80
- 4 dk
Bir düğümü aşağı kaydırarak yığın özelliğini sağlamayı öğrenirsin.
Heapify
Heapify, bir düğümü heap özelliğini bozduğu yerde aşağı kaydırarak düzeltir. Düğüm, iki çocuğuyla karşılaştırılır; büyük olanla yer değiştirilir.
Bu işlem, yaprak olmayan son düğümden köke doğru her düğüm için tekrarlanırsa tüm dizi max-heap olur. Bu O(n) işle yapılır.
Heapify, heap sort'un ve öncelikli kuyruğun temel taşıdır.
Recursion ile heapify
Heapify, recursion ile yazılabilir: düğüm büyük çocukla takas edilir, sonra aynı işlem takas yapılan çocuğa uygulanır. Temel durum: yaprak düğümdür.
İteratif yazım da yaygındır ve yığın taşması riskini önler. İkisi de O(log n) çalışır çünkü her adımda bir düzey inilir.
Büyük dizilerde iteratif tercih edilir; küçüklerde recursion okunabilir.
Uygulama Heapify (aşağı kaydır)
heapify(arr, n, i) yaz. i düğümünü max-heap için aşağı kaydır. arr=[3,9,2,1,4,5]; heapify(arr,6,0); print(arr) ile [9, 4, 5, 1, 3, 2] yazdır.
Başlangıç kodu
def heapify(arr, n, i):
# Aşağı kaydırÖrnek çözüm
def heapify(arr, n, i):
# Aşağı kaydır
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)
arr = [3, 9, 2, 1, 4, 5]
heapify(arr, 6, 0)
print(arr)Beklenen çıktı
[9, 4, 5, 1, 3, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Büyük çocuk
largest = i
if arr[left] ____arr[largest]:largest = i
if arr[left] >arr[largest]:Açıklama: > doğru.
2 Heapify: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Heapify |
Aşağı kaydır |
Büyük çocuk |
Takas |
Yaprak |
Temel durum |
Maliyet |
O(log n) |
3 Heapify ne zaman durur?
- Her zaman kökte
- Sadece yaprakta
- Yaprakta veya özellik sağlanınca Doğru cevap
- Asla
Açıklama: Yaprakta veya özellik sağlanınca