原題
給出一個整數(shù)數(shù)組毅桃，堆化操作就是把它變成一個最小堆數(shù)組阅爽。
對于堆數(shù)組A被环，A[0]是堆的根真竖，并對于每個A[i]儡蔓，A [i * 2 + 1]是A[i]的左兒子并且A[i * 2 + 2]是A[i]的右兒子。
給出** [3,2,1,4,5]疼邀，返回[1,2,3,4,5] **或者任何一個合法的堆數(shù)組
解題思路
- sift down函數(shù)可以寫成recursion也可以寫成while循環(huán)喂江，比如當(dāng)我們刪除一個最小值以后，就把最后一個值交換到頂點(diǎn)旁振，然后向下swap获询，目的就是每次找到當(dāng)前節(jié)點(diǎn)的兩個兒子中的最小值，如果小于這個最小值就互換拐袜，直到最底層吉嚣，所以deleteMin的時間復(fù)雜度是 - O(logn)
- sift up函數(shù)就是用于insert的時候，每次要往minHeap中添加一個數(shù)的時候蹬铺，首先添加到最末的位置尝哆。然后每次和它的父親節(jié)點(diǎn)相比較，如果小于父親結(jié)點(diǎn)則向上swap甜攀，操作可能一直到最頂才結(jié)束秋泄，所以insert得時間復(fù)雜度是 - O(logn)
- heapify就相當(dāng)于buildMinHeap函數(shù)琐馆，把一個無序的數(shù)組轉(zhuǎn)化成一個minHeap數(shù)組，方法就是把數(shù)組的前半段做sift down操作恒序。
- 注意如果想要在函數(shù)中整體覆蓋一個數(shù)組瘦麸，Python的寫法如下
# 正確
array[:] = newArray[:]
# 兩個錯誤示范，相當(dāng)于在函數(shù)內(nèi)改變了reference指向歧胁，并沒有實(shí)際改變原來array指向的object
array = newArray[:]
array = newArray
完整代碼
class Solution:
# @param A: Given an integer array
# @return: void
def heapify(self, A):
self.currentSize = len(A)
self.minheap = [0] + A
for i in range(len(A)//2, 0, -1):
self.minHeapify(self.minheap, i)
A[:] = self.minheap[1:]
def minHeapify(self, L, index):
if index > self.currentSize // 2:
return
if index*2+1 > self.currentSize or L[index*2] < L[index*2+1]:
minChild = index*2
if L[index] > L[minChild]:
L[index], L[minChild] = L[minChild], L[index]
self.minHeapify(L, index*2)
else:
minChild = index*2+1
if L[index] > L[minChild]:
L[index], L[minChild] = L[minChild], L[index]
self.minHeapify(L, index*2+1)
