说明

创建最大堆

代码

def build_max_heap(A:List[int]):
    n = len(A)//2
    for i in range(n,-1,-1):
        max_heapify(A,i)

param = [4,1,3,2,16,9,10,14,8,7]
build_max_heap(param)
print(param)
#[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

时间复杂度

h为节点高度,n为数量

$$\large \sum_{h=0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}}\rceil O(h) = O(n\sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h}) = O(n\sum_{h=0}^{\infty} \frac{h}{2^h}) = O(n)$$