基础堆排序学习笔记

什么是堆？

在计算机科学中，堆（Heap）是一种特殊的数据结构，它可以被看作是一棵树的数组对象。

堆分为大根堆和小根堆两种。

在大根堆中，父节点的值总是大于等于它的每个子节点的值。在小根堆中，父节点的值总是小于等于它的每个子节点的值。

堆排序算法

堆排序是一种基于堆数据结构的排序算法。

堆排序可以利用完全二叉树的特性使得它的空间复杂度更低（O(1)），但时间复杂度并不是最优的，而且不像快排那样是原址排序。

堆排序的基本思路是将待排序序列构造成一个大根堆（或小根堆），此时整个序列的最大（或最小）值就是堆顶的根节点。

将其与末尾元素进行交换，此时末尾就是最大（或最小）值。然后再调整剩余的节点使得它们满足堆的性质，然后继续交换堆顶元素和当前末尾元素，反复执行这个过程直到整个序列有序。

堆排序实例

假设我们有一个待排序序列：[6, 8, 2, 5, 9, 1, 3, 4, 7]

1. 首先将待排序序列构造成一个大根堆：

Copy Code
         9
       /   \
      8     3
     / \   / \
    6   7 2   1
   / \
  5   4

2. 将堆顶元素 9 与末尾元素 7 交换，并将序列长度减 1。此时序列变成：[6, 8, 2, 5, 7, 1, 3, 4, 9]

3. 接着对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         8
       /   \
      7     3
     / \   / \
    6   4 2   1
   /
  5

4. 将堆顶元素 8 与末尾元素 5 交换，并将序列长度减 1。此时序列变成：[5, 7, 2, 6, 4, 1, 3, 8, 9]

5. 再次对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         7
       /   \
      6     3
     / \   / \
    5   4 2   1
   /
  8

6. 将堆顶元素 7 与末尾元素 8 交换，并将序列长度减 1。此时序列变成：[5, 6, 2, 1, 4, 8, 3, 7, 9]

7. 继续对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         6
       /   \
      5     3
     / \   / \
    1   4 2   8
   /
  7

8. 将堆顶元素 6 与末尾元素 7 交换，并将序列长度减 1。此时序列变成：[5, 4, 2, 1, 3, 8, 7, 6, 9]

9. 继续对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         5
       /   \
      4     2
     / \   / \
    1   3 8   7
   /
  6

10. 将堆顶元素 5 与末尾元素 6 交换，并将序列长度减 1。此时序列变成：[4, 3, 2, 1, 7, 8, 6, 5, 9]

11. 继续对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         4
       /   \
      3     2
     / \   / \
    1   7 8   6
   /
  5

12. 将堆顶元素 4 与末尾元素 5 交换，并将序列长度减 1。此时序列变成：[3, 1, 2, 6, 7, 8, 5, 4, 9]

13. 继续对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         3
       /   \
      1     2
     / \   / \
    6   7 8   5
   /
  4

14. 将堆顶元素 3 与末尾元素 4 交换，并将序列长度减 1。此时序列变成：[1, 6, 2, 5, 7, 8, 4, 3, 9]

15. 继续对剩余的元素重新构造大根堆。此时序列变成：

Copy Code
         1
       /   \
      6     2
     / \   / \
    5   7 8   4
   /
  3

16. 将堆顶元素 1 与末尾元素 3 交换。此时排序完成，得到有序序列：[1, 2, 3, 4, 5, 6, 7, 8, 9]