说明

维护某个节点在最大堆中的位置

代码

from typing import List
import math
def parent(i:int)->int:
    return (i-1)//2
def left(i:int)->int:
    return 2*i+1
def right(i:int)->int:
    return 2*i+2
def max_heapify(A:List[int],i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[l] > A[i]:
        largest = l
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i],A[largest]=A[largest],A[i]
        max_heapify(A,largest)
param = [16,14,10,4,7,9,3,2,8,1]
max_heapify(param,3)
print(param)
# [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

时间复杂度

$$T(n) \leq T(2n/3) + \Theta(1) =O(\lg n) \$$