堆排序

[!quote] 堆排序 堆排序 是一种利用二叉堆实现的排序算法。

• 核心思想：把一个无序数组构造成一个堆结构，使之有序
• 步骤
  • 将数组构建成堆
  • 跟据某种规则下沉非叶子节点，重新调整堆
  • 一直重复，直到满足二叉堆

• 构建最大堆

1. 原数组 [4, 10, 3, 5, 1]
        4
       / \
     10   3
    / \
   5   1

2. 找到最后一个非叶子节点，也就是10，其左子节点5，和右子节点1都小于本身10，所以不动
3. 再往上找非叶子节点，也就是4，其左子节点10大，所以我们交换4和10，变成 [10, 4, 3, 5, 1]
	10
   /  \
  4    3
 / \
5   1

4. 重复这个过程
5. 已经满足最大堆的规则了，构建完成 [10, 5, 3, 4, 1]
        10
       /  \
     5     3
    / \
   4   1