目录
一、堆排序之树的基础知识
1. 树的定义
2. 树的一些概念
二、堆排序二叉树的基本知识
1. 二叉树的定义
2. 二叉树的存储方式（表达方式）
2.1 顺序存储方式
三、堆
1. 堆的定义
2. 堆的向下调整性质
四、堆排序的过程
1. 建造堆
五、时间复杂度
六、内置模块
一、堆排序之树的基础知识
1. 树的定义
- 树是一种数据结构 比如：目录结构
- 数是一种可以递归定义的数据结构
- 树是由n个节点组成的集合：
- 如果n = 0，那这是一棵空树；
- 如果n > 0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身优势一棵树。
2. 树的一些概念
- 根节点、叶子节点：根节点如下图的A；叶子节点：不能分叉的节点为叶子节点（BCHIKLMNPQ）
- 树的深度(即结构共有几层，如下图树的结构有4层，A为第1层，P,Q为第4层)
- 树的度（即在树中，那个节点的分叉数最多，如下图中的A，树的度为6）
- 孩子节点/父节点（如E节点中，E是I的父节点；I是E的子节点）
- 子树（整个树中的一部分，例如EIJQO即为子树。）
二、堆排序二叉树的基本知识
1. 二叉树的定义
二叉树：度不超过2的树，即每个节点最多有两个孩子节点，且两个孩子节点被区分为左孩子节点和右孩子节点。
满二叉树：一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。（从满二叉树最后一层拿走几个节点；即相对于满二叉树，最下面一层可以不满，但必须从左到右依次排过来）
2. 二叉树的存储方式（表达方式）
- 链式存储方式
- 顺序存储方式（堆排序，用列表来存）
2.1 顺序存储方式
观察上图父节点 和孩子节点的编号下标的关系
1. 父节点与左孩子节点的编号下标的关系：
- 0-1 1-3 2-5 3-7 4-9
- i → 2i+1
2. 父节点与右孩子节点的编号下标的关系：
- 0-2 1-4 2-6 3-8 4-10
- i → 2i+2
三、堆
1. 堆的定义
堆：一种特殊的完全二叉树结构。
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
2. 堆的向下调整性质
向下调整性质：假设根节点的左右子树都是堆，但根节点 ，那么可以通过一次向下的调整来将其变成一个堆。
如下图所示：
通过将2往下移，9往上移动使得整体成为一个堆。
如下图所示：
四、堆排序的过程
步骤：
- 建立堆
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
- 堆顶元素为第二最大元素
- 重复步骤3，直到堆变空
1. 建造堆
首先看最下面的元素是否满足条件，即看最后面的非叶子节点。
再接着调整上面的，先调整小的，再调整大的，最后调整整个（农村包围城市），当调整整个的时候，也就是除了堆顶元素其他下面的元素都有序，此时我们采用向下调整的性质。
例如下图中需要调整五次，从3开始，倒序到6.
注意：不管左孩子还是右孩子，他们父节点的坐标都为（n-1）// 2
我们先写向下调整函数的代码：
def sift(li, low, high): # 向下调整函数；初始条件应该为除了根节点，下面的子堆默认为有序的
"""
:param li: 列表
:param low: 根节点位置
:param high: 根的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # 左孩子
tmp = li[low] # 将堆顶元素存起来
while j <= high: # 只要j上面有数，没跑到结构外
if j + 1 <= high and li[j + 1] > li[j]: # 存在右孩子，且右孩子比左孩子大；不能交换
j = j + 1 # j指向有孩子
if li[j] > tmp:
li[i] = li[j] # 换数
i = j # 往下看一层
j = 2 * i + 1
else: # 此时tmp更大，将tmp放回原位
li[i] = tmp
break # 直接退出，因为sift默认下面就是堆的情况下
else: # 两种退出循环的条件；当其越界
li[i] = tmp当写完向下调整函数后，我们发现，如果我们需要对堆来排序，在对每个部分进行调整，最后调整整个部分（构建堆）。
def heap_sort(li):
n = len(li)
for i in range((n - 2)//2, -1, -1): # i表示构建堆的时候调整的根的部分的下标
sift(li, i, n - 1) # 一直将整个堆的最后一个元素当作high，因为high作用在这里起比较的作用，判断是否越界。
for i in range(n-1, -1, -1): # i此时为最后一个元素
li[0], li[i] = li[i], li[0] # 将堆顶元素与最后一个元素换位置
# 交换后i位置的元素前往堆顶，堆顶的元素放置一旁，i的元素空出来，此时最后一个元素为i-1
sift(li, 0, i-1) # 针对整个堆进行排构建堆之后，再重复上述的2，3，4步骤。
最终即可对整个堆排完序。
示例的综合代码如下所示：
def sift(li, low, high): # 向下调整函数；初始条件应该为除了根节点，下面的子堆默认为有序的
"""
:param li: 列表
:param low: 根节点位置
:param high: 根的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # 左孩子
tmp = li[low] # 将堆顶元素存起来
while j <= high: # 只要j上面有数，没跑到结构外
if j + 1 <= high and li[j + 1] > li[j]: # 存在右孩子，且右孩子比左孩子大；不能交换
j = j + 1 # j指向有孩子
if li[j] > tmp:
li[i] = li[j] # 换数
i = j # 往下看一层
j = 2 * i + 1
else: # 此时tmp更大，将tmp放回原位
li[i] = tmp
break # 直接退出，因为sift默认下面就是堆的情况下
else: # 两种退出循环的条件；当其越界
li[i] = tmp
# 从孩子找父亲为（n-1）// 2；最后一个节点下标为n-1，则最后一个非叶子结点的下标为（n-2）//2
def heap_sort(li):
n = len(li)
for i in range((n - 2) // 2, -1, -1): # i表示构建堆的时候调整的根的部分的下标
sift(li, i, n - 1) # 一直将整个堆的最后一个元素当作high，因为high作用在这里起比较的作用，判断是否越界。
# 构建堆结束
for i in range(n - 1, -1, -1): # i此时为最后一个元素
li[0], li[i] = li[i], li[0] # 将堆顶元素与最后一个元素换位置
# 交换后i位置的元素前往堆顶，堆顶的元素放置一旁，i的元素空出来，此时最后一个元素为i-1
sift(li, 0, i - 1) # 针对整个堆进行排序
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)五、时间复杂度
首先对于我们的sift函数，其时间复杂度为O(logn).
def sift(li, low, high):
i = low
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
break
else:
li[i] = tmpsift最多走一个数的高度层，因此其复杂度相当于分半，为logn。
对于heap_sort，时间复杂度为（n/2 * logn）+（n-1）*logn = O(logn)（两个for循环）
六、内置模块
堆排序在Python中存在内置模块（heapq）（import heapq）（q为queue 优先队列）
常用函数：
- heapofy(x) #建堆
- heappush(heap, item)
- heappop(heap) #每次弹出一个最小元素
示例代码如下：
import heapq
import random
li = [i for i in range(100)]
random.shuffle(li)
print(li)
heapq.heapify(li) #先建堆
n = len(li)
for i in range(n):
print(heapq.heappop(li),end = ",")输出结果如下：
