目录
在上篇文章学习了算法入门——插入排序、快速排序，这篇文章学习算法入门——堆排序。
堆
堆是一种特殊的完全二叉树结构，堆可以分为大根堆和小根堆，其中
大根堆：一棵完全二叉树，满足任一节点都比其子节点都大；
小根堆：一棵完全二叉树，满足任一节点都比其子节点都小；
如下图所示：
9比8大，8比6大，1比2小，2比3小。
堆的向下调整
当根节点的左右子树都是堆时，但根节点不满足堆的性质，如下图所示：
由于根节点为3且该堆为大根堆，不满足比其子节点都大，所以需要进行一次向下调整来把该二叉树变为堆。
向下调整过程如下：
首先把根节点3取出来，再对比左右子树的根节点大小，大的放在根节点中，如下图所示：
由于9比7大，所以9被放在根节点，那么原来存放9的位置就空了，接下来8与6对比，大的放在9原来的位置，如下图所示：
接下来2与4对比，4比2大，4就放在8原来的位置，最后把堆最初的根节点3放在4原来的位置上，如下图所示：
这样就成功把二叉树转变为堆了。
在上面最初的二叉树转换为列表：3,9,7,8,6,0,1,2,4,5，向下调整示例代码如下：
def sift(li, low, high):
i = low # i最开始指向根节点，也就是列表的第一个元素下标
j = 2 * i + 1 # 左子树的节点开始
tmp = li[low] # 把堆顶元素保存，也就是保存列表的第一个元素
while j <= high: # 只要还有叶子节点
if j + 1 <= high and li[j + 1] > li[j]: # 如果有且右子树比较大
j = j + 1 # 把左子树的节点与堆顶元素比较大小改为与右子树的节点比较大小
if li[j] > tmp: # 当堆顶元素小于子节点的元素时
li[i] = li[j] # 子节点元素放在节点位置
# 比较下一层节点
i = j
j = 2 * i + 1
else：
li[i]=tmp # 否则该堆顶元素该节点上
else:
li[i]=tmp # 把tmp放在该节点上
print(li)
li=[3,9,7,8,6,0,1,2,4,5]
sift(li,0,len(li)-1)
运行结果如下：
这样就把非堆转换为堆了。
构造堆
如何把如下图的二叉树转换为堆呢？
首先我们通过对比叶子节点和子节点大小，大的往上提，如下图所示：
5和4交互位置后，根据下图红框的顺序比较大小，大的移动到节点上，如下图所示：
最终得出的堆如图所示：
简单来说就是把每个节点与其叶子节点比较大小，通过向下调整的方法把节点与叶子节点位置交换。
示例代码如下：
def heap_sort(li):
n=len(li) # n为列表的长度
for i in range((n-2)//2,-1,-1): # 从列表后面开始遍历
# i表示建堆的时候调整部分的根的下标
sift(li,i,n-1) # 调用刚才编写的向下调整函数
这样就可以把一个二叉树转换为堆。
堆排序
我们成功把非堆的二叉树转换为堆，但堆转换的列表并不是排好序。
由于堆顶肯定是最大的元素，这时我们可以每次把堆顶提取出来，再把堆最后的叶子节点放在堆顶，通过堆的向下调整来调整堆元素，这时堆顶又变为了堆中最大的元素，再提取堆顶，这样反复就可以把堆排好序了。如下图所示：
首先把堆顶元素提取出来，再把最后面的叶子节点放在堆顶，如下图所示：
通过向下取整把该二叉树变为堆，再通过刚才的步骤提取堆顶，这样方法就可以把列表排好序。
示例代码如下：
def last(li):
n=len(li)
for i in range(n - 1, -1, -1): # 从列表后面开始遍历
# i指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1) # i-1是最新的叶子节点
print(li)
堆排序完整代码如下：
# 堆的向下调整
def sift(li, low, high):
i = low # i最开始指向根节点，也就是列表的第一个元素下标
j = 2 * i + 1 # 左子树的节点开始
tmp = li[low] # 把堆顶元素保存，也就是保存列表的第一个元素
while j <= high: # 只要还有叶子节点
if j + 1 <= high and li[j + 1] > li[j]: # 如果有且右子树比较大
j = j + 1 # 把左子树的节点与堆顶元素比较大小改为与右子树的节点比较大小
if li[j] > tmp: # 当堆顶元素小于子节点的元素时
li[i] = li[j] # 子节点元素放在节点位置
# 比较下一层节点
i = j
j = 2 * i + 1
else：
li[i]=tmp # 否则该堆顶元素该节点上
else:
li[i]=tmp # 把tmp放在该节点上
return li
# 构建堆
def structure_heap(li):
n = len(li)
for i in range((n - 2) // 2, -1, -1):
# i表示建堆的时候调整部分的根的下标
sift(li, i, n - 1)
print('构造的堆：',li)
heap_last(li)
# 堆排序
def heap_last(li):
n=len(li)
for i in range(n - 1, -1, -1):
# i指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1) # i-1是新的high
print('堆排序后:',li)
li=[2,4,5,1,9,8,6,7,3,0]
print('原始列表:',li)
structure_heap(li)
运行结果如下图：
堆排序的时间复杂度为：O(nlogn)。
好了，关于算法入门——堆排序就学到这里了，下篇文章学习算法入门——归并排序、希尔排序。
公众号：白巧克力LIN
该公众号发布Python、数据库、Linux、Flask、自动化测试、Git、算法等相关文章！
- END -