İçeriğe geç

Heapify ve sift

Ders 2 / 7 · 6 dk

Heapify ve sift

Adım 1/14

Karışık bir dizi, heap değil. Düzeltmek bütün diziye asla dokunmaz; her yanlış değer tek bir yol yürür.

Fikir

Bir heap'i düzeltmek asla dizinin tamamına dokunmaz. Fazla büyük bir değer, küçük çocuğuyla (child) yer değiştirerek (swap) yapraklara doğru batar; fazla küçük bir değer köke doğru yükselir. İki durumda da tek bir yolu izler: en fazla log n yer değiştirme.

Karışık bir değer listesinden heap kurmak için son ebeveynden (parent) başlayıp sift down yap ve geriye doğru ilerle. Bu O(n) tutar, çünkü çoğu düğüm (node) zaten alta yakındır.

Gerçek hayattan örnek

Bir su arıtma tesisinin çöktürme havuzu bunu kimse karıştırmadan yapar. Ağır tortu, kendinden ağır bir şeye rastlayana kadar katman katman batar; köpük, kendinden hafif bir şeye rastlayana kadar yükselir. Hiçbir şey tüm havuzla karşılaştırılmaz; her parçacık yalnız yanı başındaki komşularıyla pazarlık eder.

Kod

Sıra sende

Adımları doğru sıraya koy.

  1. İkisinin yerini değiştir, sonra çocuğun konumundan devam et
  2. En alt seviyenin hemen üstündeki son ebeveynden başla
  3. Bir indeks sola geç ve 0 indeksi bitene kadar tekrarla
  4. Düğümü, iki çocuğundan küçük olanla karşılaştır

Mini quiz

1 / 3

Bir min-heap'te konumu için fazla büyük olan bir değer nasıl hareket eder?