前言
堆排序需要将一颗完全二叉树构建成一个大顶堆或者小顶堆,然后将堆顶和最后的数字交交换
什么是大顶堆?
堆顶一定是最大值,父结点一定是三个值之间最大的值。小顶堆与其相反。
其中最大值为堆顶,第二层一定有一个次大值
其中最大值为堆顶,第二层一定有一个次大值
二叉树的性质四
- 具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思
- int(math.log(n)) + 1
二叉树的性质五
如果有一颗n个结点的完全二叉树(深度为性质4).结点按照层序编号(i),如下:
1
2 3
4 5 6 7
8 9 10
- 如果i=1,则结点i是二叉树的根,无双亲;
- 如果i>1,则其双亲是
int(i/2)
,向下取整。就是子节点的编号除以2得到的就是父结点的编号。 - 父结点如果是i,那么左孩子结点就是
2i
,右孩子结点就是2i+1
- 如果
2i>n
,则结点i无左孩子,即结点i为叶子结点;否则其左孩子结点存在编号为2i
n>2i
说明存在右孩子, 且标号为:2i+1
- 如果
2i+1>n
,则结点i无
右孩子,注意这里并不能说明结点i没有左孩子;否者右孩子结点存在编号为2i+1
- 完全二叉树父亲结点一共有 n//2 个(包含根结点)
打印二叉树
构建大顶堆
20
40 50
构建单个二叉树
如上面的大顶堆,我们先判断改大顶堆是否有左孩子,然后判断右孩子
如果 有左孩子,我们假设左孩子是最大的那个树
然后判断是否有右孩子,如果有左孩子和右孩子比较,如果右孩子大于左孩子,保存右孩子为最大值
最后和父结点进行比较,如果大于父结点就交换位置,否则不变
代码实现
def max_heap(i, n, array):
"""
调整数据为大顶堆
:param i: 根节点的标号
:param n: 结点个数
:param array: 带构建的数据
:return: list 构建好的大顶堆
"""
while 2 * i <= n:
# 性质五:如果2i>n,则结点i无左孩子
# 这里表示有左孩子就进入循环
l_index = 2 * i
# 左孩子编号 2i
max_index = l_index
# 假设最大的就是左孩子,这里保存索引
if 2 * i + 1 <= n and array[l_index] < array[2 * i + 1]:
# 如果存在右孩子且右孩子大于左孩子,最大值索引为右孩子
max_index = 2 * i + 1
if array[max_index] > array[i]:
# 最大值和根结点比较,如果最大值真的大于根节点,则交换位置
array[max_index], array[i] = array[i], array[max_index]
i = max_index
# 修正i,继续向下调整直到不存在孩子结点
else:
# 没有孩子结点就退出循环
break
return array
全面调整二叉树为大顶堆
上面的算法从堆顶构建的话,不能达到我们的目的,但是从最后一个父结点开始就可以达到我们的目的
代码实现
def all_heap(total, array):
"""
调整整个数据为大顶堆
:param total: 结点个数
:param array: 结点列表
:return: list
"""
for i in range(total//2, 0, -1):
# 父亲结点个数: 结点数 // 2
max_heap(i, total, array)
# 因为这里全是引用类型,没有拷贝数据。节省了内存空间
# 从最后一个父结点开始调整
return array
升序排序
将堆顶和最后一个交换,然后重新构建大顶堆
然后根系结点和最后一个结点进行交换
注意这里最后一个不是
90
,而是20
, 90
已经不再参与大顶堆构建
依次内推
代码实现
origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]
origin = all_heap(len(origin) - 1, origin)
# 构建大顶堆, 其实没有执行任何拷贝,直接调用函数就可以实现对origin的更改
def sort(total, array):
"""
排序
:param total: 结点个数
:param array: 结点列表
:return: list
"""
while total > 1:
array[total], array[1] = array[1], array[total]
total -= 1
max_heap(1, total, array)
# 重构大顶堆,因为不要最后一个结点参与,所以total - 1
if total == 2 and array[total] >= array[total - 1]:
# 如果 标号为2的结点 大于或等于根节点就不做调整了
break
return array
到此,排序完成
list
类型,如果不进行拷贝的话,不管怎么引用,他们都是表示的同一段内存空间,修改任何一个引用标识符相当于修改其他标识符的数据,如a = [1, 2], b = a, a.append(3), print(b) = > 1,2,3