[数据结构与算法]堆排序算法图例解析

1. 二叉树
2. 二叉堆
3. 推排序

在讲堆排序之前，先了解一下二叉树和二叉堆吧！

二叉树

二叉树的结构：

• 根节点：图中的a
• 叶子节点：没有子节点但是有父节点：图中的f,w就是叶子节点
• 分支节点：既有子节点又有父节点
• 节点的度：一个节点所含有的子节点的个数被称为该节点的度

二叉树的特点：

• 二叉树的节点最大的度数为2(如下图所示，最大的节点的度都为2)
• 二叉树有左右子节点之分
• 二叉树第i层的节点数至多为2^i-1（如下图所示第2层节点数为2^2-1=2）
• 对于n层的二叉树，其所有节点数最多为2ⁿ-1(如下图所示所有节点数为2⁴-1=15)

完全的二叉树：

• 所有叶子节点都分别出现在第h层或者h-1层（如下图所示节点7，节点8，9，10，11，12都是叶子节点）
• 只允许最后一层的右边有空缺
• 度为1的节点只有一个或者0个（如下图所示节点6）
• 第i层最多只能有2^i-1
• 对于n层的二叉树，其所有节点数最多为2^n-1
  

二叉堆

堆排序

第一部分的排序，将堆顶的元素截掉，放到后面去

第二次排序，也是和上面的一样，再找多几次堆顶的元素，然后截掉，然后放到后面-1（意思就是想进的在最后面）