Heapify

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.

Örnek çözümü göster

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)

Kendini test et

Büyük çocuk

largest = i
if arr[left] ____arr[largest]:

Cevabı göster

largest = i
if arr[left] >arr[largest]:

Heapify: kavramları eşleştir

Heapify

Aşağı kaydır
Büyük çocuk

Takas
Yaprak

Temel durum
Maliyet

O(log n)
Heapify ne zaman durur?
- Her zaman kökte
- Sadece yaprakta
- Yaprakta veya özellik sağlanınca
- Asla
Cevabı göster

Yaprakta veya özellik sağlanınca — Yaprakta veya özellik sağlanınca

Sıradaki ders: Build heap ve sırala

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler