İçeriğe geç

Listeyi yerinde heapify et

Kolay#heapify#sift-down~15 dk

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

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

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

Python 3Ctrl+Enter çalıştırır