建堆
堆的建立
建堆主要有两种方式，两种方式的复杂度不同。
- 自顶向下建堆，从根节点开始，将节点依次插入到堆中，并进行下沉操作，复杂度为
- 自底向上建堆，对于n个节点的树，第一个非叶子节点位于
处，因此从该结点开始，依次进行下沉，复杂度为
自底向上建堆
def sink(nums,root):
print(nums)
if 2*root+1 < len(nums):
k = 2*root+2 if 2*root+2 < len(nums) and nums[2*root+2] < nums[2*root+1] else 2*root+1
if nums[root] > nums[k]:
(nums[root], nums[k]) = (nums[k], nums[root])
sink(nums, k)
def heapify(nums):
for i in range(len(nums)//2-1, -1, -1):
print(i)
sink(nums, i)
print(nums)
x = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapify(x) 时间复杂度证明
对于一颗满二叉树，第i层有
个节点；建堆过程自底向上，基本操作为)
的交换操作。
最坏的情况下，第i层的节点需要经过h-i次交换操作才能完成该节点的建堆过程，h为树的总层数；
因此时间复杂度计算如下：
用错位相减法进行计算可以得到：
对于一共有h层的树来说，总节点数为：
，渐进时忽略末尾的1，取
，则：
