İçeriğe geç

Dizi min-heap mi

Kolay#heap#array-as-tree~15 dk

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

Hedef zaman
O(n)
Hedef alan
O(1)

Kısıtlar

  • the list may be empty

Kodda değil de fikirde mi takıldın? Heapify ve sift bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case