Dizi min-heap mi
Görev tanımı
Problem
Bir sayı listesi ikili bir ağaç olarak okunabilir: i indeksindeki değerin çocukları, varsa, 2i + 1 ve 2i + 2 indekslerindedir. Listenin zaten min-heap kuralını sağlayıp sağlamadığına, yani hiçbir değerin çocuklarından herhangi birinden büyük olmadığına karar ver. Sağlıyorsa True, değilse False döndür. Boş liste ya da tek değer geçerli bir heap sayılır.
Örnekler
Input: values = [1, 3, 2, 7, 4]
Output: True
Neden: 1, 3 ile 2'nin; 3 de 7 ile 4'ün üstünde
Input: values = [2, 1, 3]
Output: False
Neden: kök 2 sol çocuğu 1'den büyük
Input: values = [5, 5, 5]
Output: True
Neden: edge case: eşit değerler kuralı asla bozmaz
İpuçları
0 / 3
Hiçbir zaman bir ağaç kurmana gerek yok. İndeks aritmetiği kimin kimin ebeveyni olduğunu zaten söylüyor.
Her ebeveyn kendi çocuklarından büyük değilse kural en aşağıya kadar geçerlidir, çünkü küçük ya da eşit ilişkisi zincirlenir.
1'den sona kadar her indeksi dolaş, ebeveynini (i - 1) // 2'de bul ve bir ebeveyn çocuktan büyük olduğu anda başarısız ol. Dolaşma biterse liste bir heap'tir.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- the list may be empty
Çözüm
Heap kuralı yereldir: her ebeveyn çocuklarından büyük değilse her ata her torundan büyük değildir, çünkü karşılaştırmalar zincirlenir. Bu yüzden kök olmayan her indeksi (i - 1) // 2'de yaşayan ebeveyniyle kontrol etmek yeter. Çocuk tarafından kontrol etmek her ebeveyn-çocuk çiftini tam bir kez ziyaret eder. Zaman O(n), alan O(1).
def is_min_heap(values):
for child in range(1, len(values)):
parent = (child - 1) // 2 # the array position of this value's parent
if values[parent] > values[child]:
return False # one broken pair is enough to fail
return True
print(is_min_heap([1, 3, 2, 7, 4])) # -> True
print(is_min_heap([2, 1, 3])) # -> False
print(is_min_heap([5, 5, 5])) # -> TrueKodda değil de fikirde mi takıldın? Heapify ve sift bunu anlatıyor.