|
最小堆 建堆和排序
PS：? ? ? ? 以下为最小堆
????????????????根节点为数组下标为0的元素。? ? ? ? 父节点： i ?子节点： 2*i+1 ?2*i+2??
建堆：插入到最后 向上堆化 ? ?给出子节点下标即可
? ? ①father = (son-1)//2 ?判断father是否比son所指元素大 是则调换
? ? ②将father赋值给son 重复执行① 直到 son = 0 ?返回
堆排序：将根节点与最后元素互换 ?向下堆化 ?给出最终父节点的最大下标t即可 ? 父节点初始下标为 0
? ? ① 找到子节点中最小的值对应的下标son ? ?son1=father*2+1 son2=father*2+2
? ? ② 判断father是否比son所指元素大,是则调换
? ? ③ 将son赋值给father 重复执行①② 直到 father > t 返回
复杂度：? ? ? ? 时间 O(nlogn)? ? ? ?空间 O(1)
代码：
def conheap2(nums):
def insertheap(son):
if son == 0:
return
father = (son-1)//2
if nums[father] > nums[son]:
nums[father], nums[son] = nums[son], nums[father]
insertheap(father)
for i in range(len(nums)):
insertheap(i)
# 堆排序
def myheapSort2(nums):
def delheap(father, threshold):
son1, son2 = father * 2 + 1, father * 2 + 2
if son1 > threshold:
return
son = son1
if son2 <= threshold and nums[son2] < nums[son1]:
son = son2
if nums[father] > nums[son]:
nums[father], nums[son] = nums[son], nums[father]
delheap(son, threshold)
for i in range(len(nums)-1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
delheap(0, i-1)
路虽远，行则将至。事虽难，做则必成?
|