排序算法 （08.堆排序）
2021-02-10 13:18
标签：遍历 调整 ret range while build uil 父节点 思路 排序算法 （08.堆排序） 标签：遍历 调整 ret range while build uil 父节点 思路 原文地址：https://www.cnblogs.com/jackson1/p/12742291.html什么是堆
1.所有 父节点 的值 都大于 （小于）子节点 的 值
2.属于完全 二叉树
堆排序思路
1.先定义一个调整堆的函数， 保证以 某点为 父节点进行调整， 并且保证 不 打乱
子节点 以下的 子树的 堆结构 ， 所以 用到 递归思想
2.从头遍历 到 树尾， 先进行 首尾交换， 再进行 构建 堆
代码实现
# 堆调整:
def heapify(tree, n, i):
if i >= n:
return
max = i
c1 = 2*i + 1
c2 = 2*i + 2
if tree[c1] and tree[c1] > tree[max]:
max = c1
if tree[c2] and tree[c2] > tree[max]:
max = c2
if max != i :
#交换两个值
tree[max], tree[i] = tree[i], tree[max]
heapify(tree , n, max)
#build堆
def build_heap(tree, n):
i = (n - 1) / 2
while i >= 0:
heapify(tree, n, i)
i -= 1
#堆排序
def heap(tree, n):
for i in range(0, n):
tree[n-1],tree[0] = tree[0],tree[n-1]
build_heap(tree, n-1)