Listeyi yerinde heapify et
Görev tanımı
Problem
Bir sayı listesini heapq modülü olmadan in-place (yerinde) bir min-heap'e dönüştür ve döndür. Bir listede saklanan bir min-heap'te i indeksinin çocukları 2i + 1 ve 2i + 2'dedir ve her ebeveyn çocuklarının her birinden büyük değildir. Aşağıdan yukarı yöntemi kullan: son ebeveynden başlayıp köke doğru ilerleyerek her ebeveyni aşağı elet; böylece bütün kurulum O(n)'de çalışsın.
Örnekler
Input: nums = [5, 3, 8, 1, 2]
Output: [1, 2, 8, 3, 5]
Neden: 3 çocuğu 1 ile yer değiştirir, sonra 5 kökten 1 ve 2'nin altına iner
Input: nums = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 6, 5, 4, 7, 8, 9]
Input: nums = [42]
Output: [42]
Neden: edge case: tek eleman zaten bir heap
İpuçları
0 / 3
Yapraklar zaten bir boyutlu heap'lerdir, yani listenin ikinci yarısı için yapılacak bir şey yok. Çocuğu olan son indeks n // 2 - 1.
Aşağı eleme, iki alt ağacı zaten heap olan tek bir ebeveyni düzeltir: o çocuk ondan küçük olduğu sürece onu küçük çocuğuyla yer değiştir ve aşağı doğru izle.
i için n // 2 - 1'den 0'a kadar aşağı eleme çağır. Geriye gitmek, i'nin iki alt ağacının da i'den önce düzeltildiğini garanti eder.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Aşağıdan yukarı heapify listeyi bir ağaç olarak ele alır ve onu en alttaki ebeveynlerden yukarı doğru onarır. Aşağı eleme yalnız bir düğümün iki alt ağacı zaten heap iken çalışır; indeksleri n // 2 - 1'den 0'a kadar işlemek bunu garanti eder, çünkü her çocuğun indeksi daha büyüktür ve önce ele alınmıştır. Her aşağı eleme, hiçbir çocuk daha küçük olmayana kadar düğümü küçük çocuğuyla yer değiştirir (swap); bu da o alt ağaçtaki heap düzenini geri getirir. Değerleri birer birer push etmek O(n log n) tutardı, ama burada düğümlerin çoğu alta yakın durur ve yalnız bir iki seviye inebilir: toplam iş O(n) eder. Her şey listenin içinde olduğu için alan O(1).
def sift_down(a, i, n):
while True:
smallest, left, right = i, 2 * i + 1, 2 * i + 2
if left < n and a[left] < a[smallest]:
smallest = left
if right < n and a[right] < a[smallest]:
smallest = right
if smallest == i: # both children are larger: done
return
a[i], a[smallest] = a[smallest], a[i]
i = smallest # follow the value down
def heapify(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # last parent back to the root
sift_down(a, i, n)
return a
print(heapify([5, 3, 8, 1, 2])) # -> [1, 2, 8, 3, 5]
print(heapify([9, 8, 7, 6, 5, 4, 3, 2, 1])) # -> [1, 2, 3, 6, 5, 4, 7, 8, 9]
print(heapify([42])) # -> [42]Kodda değil de fikirde mi takıldın? Heapify ve sift bunu anlatıyor.