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.
- İkisinin yerini değiştir, sonra çocuğun konumundan devam et
- En alt seviyenin hemen üstündeki son ebeveynden başla
- Bir indeks sola geç ve 0 indeksi bitene kadar tekrarla
- Düğümü, iki çocuğundan küçük olanla karşılaştır
Mini quiz
1 / 3