从上往下, 从左往右, 依次将元素追加至列表中, 可以得到如下规律:
父节点和左孩子节点的坐标关系为:
0-->1 1-->3 3-->7
即: i --> 2i+1
父节点和左孩子节点的坐标关系为:
0-->2 2-->6 1-->4 3-->7
即: i --> 2i+2
满二叉树: 一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树(满二叉树), 即每层节点数都满了
完全二叉树: 从根结点到倒数第二层满足完美二叉树(满二叉树)，最后一层可以不完全填充，其叶子结点都靠左对齐。
堆是一种特殊的完全二叉树结构, 堆分为大根堆和小根堆
一个自身并不是堆的完全二叉树(根节点的值并不比其孩子节点的值大), 但其左右子树都是堆
向下调整后:
前面将一个二叉树通过顺序存储方式存在一个列表中, 反过来, 可以将待排序列表按顺序构造成一个二叉树, 如列表:
[6, 8, 1, 9, 3, 0, 7, 2, 4, 5]
构造成二叉树就是:
将二叉树构建成堆:
最终形成的堆为:
由于在构建堆和堆排序的过程中, 都需要用到向下调整, 所以我们先将向下调整的代码实现出来
如调整前为：
def shift(nums):
# 提取堆顶的值
i = 0
# 只要i有左孩子, 则继续循环
while 2*i+1 < len(nums):
# 提取i的左孩子
index_left = 2*i+1
value_left = nums[index_left]
# 提取i的右孩子
index_right = index_left+1
# 判断是否存在右孩子, 不存在则认为其值为-1
value_right = nums[index_right] if index_right < len(nums) else 0
# 比较当前值和左右孩子三者哪个大
# 若当前值大, 则无需进行调整, 结束循环
if nums[i] >= value_left and nums[i] >= value_right:
break
elif value_left >= value_right:
nums[i], nums[index_left] = nums[index_left], nums[i]
i = index_left
else:
nums[i], nums[index_right] = nums[index_right], nums[i]
i = index_right
print(nums)
调整后结果为: [9, 6, 8, 4, 5, 7, 1, 2, 0, 3]
上面的代码是针对一个完整的二叉树进行向下调整, 是从顶点开始的
而在构建堆的过程中, 是对二叉树的一部分子树依次进行向下调整的, 所以这个调整的父节点不能直接从顶点开始, 而是可以动态指定调整的父节点.
并且在堆排序的过程中, 由于我们是原地排序, 需要将顶点的位置和列表末尾的位置进行互换, 再进行向下调整, 然后末尾指针向前移动一位, 再和顶点位置进行互换, 继续向下调整, 直到排序完. 因此我们也需要动态指定调整的末尾节点.
因此添加两个参数, 依次指向调整的顶点和末尾节点
def shift(nums, top, low):
# 提取堆顶的值
i = top
# 只要i有左孩子, 则继续循环
while 2*i+1 <= low:
# 提取i的左孩子
index_left = 2*i+1
value_left = nums[index_left]
# 提取i的右孩子
index_right = index_left+1
# 判断是否存在右孩子, 不存在则认为其值为-1
value_right = nums[index_right] if index_right <= low else 0
# 比较左右孩子哪个大, 大者和i进行互换
# 若当前值大, 则无需进行调整, 结束循环
if nums[i] >= value_left and nums[i] >= value_right:
break
elif value_left >= value_right:
nums[i], nums[index_left] = nums[index_left], nums[i]
i = index_left
else:
nums[i], nums[index_right] = nums[index_right], nums[i]
i = index_right
print(nums)
将一个数组进行堆排序的过程分为两步:
def heap_sort(nums):
# 建堆: 从最后一个父节点开始, 从右往左, 从下往上, 依次对父节点进行向下调整, 最终会构建成一个堆
# 父节点(下标i)的左孩子下标为2*i+1, 右孩子下标为2*i+2
# 左孩子和右孩子(下标j)的父节点(j-1)//2, 因此最后一个父节点坐标为(len(nums)-1-1)//2
for i in range((len(nums) - 1 - 1) // 2, -1, -1):
shift(nums, i, len(nums) - 1)
# 对堆进行排序: 将堆顶和堆尾进行互换, 再进行向下调整, 堆尾向前移动一位, 继续互换和调整, 知道指针指向堆顶
for i in range(len(nums)-1, -1, -1):
# 首位替换
nums[i], nums[0] = nums[0], nums[i]
# 进行向下调整
shift(nums, 0, i-1)
执行结果:
if __name__ == ‘__main__‘:
lst = [6, 8, 1, 9, 3, 0, 7, 2, 4, 5]
heap_sort(lst)
print(nums)
# 打印结果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
原文：https://www.cnblogs.com/gcxblogs/p/14891491.html