Heapsort 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

• Java 的 PriorityQueue 的实现方式就是堆排序。

完全二叉树表示堆

完全二叉树（Complete Binary Tree）是一种二叉树，其中除了最后一层，其他层的节点数都是满的，最后一层的节点都靠左对齐。下面是一个完全二叉树的示意图：

        1
      /   \
     2     3
    / \   /
   4   5 6

堆是一种完全二叉树，堆的特点是根节点的值最小（小顶堆）或最大（大顶堆），并且任意非根节点i的值都不大于（或不小于）其父节点的值。

这是一颗包含整数 1, 2, 3, 4, 5, 6, 7 的小顶堆：

      1
     / \
    2   3
   / \ / \
  4  5 6  7

这是一颗大顶堆。

            8
          /   \
         7     5
        / \   / \
       6   4 2   1

数组存储堆元素

因为完全二叉树的结构比较规则，所以可以使用数组来存储堆的元素，而不需要使用指针等额外的空间。

在堆中，每个节点的下标和其在数组中的下标是一一对应的，假设节点下标为i，则有

• 父节点下标为i/2
• 左子节点下标为2i，
• 右子节点下标为2i+1。

例子

假设有一个数组arr=[10, 20, 15, 30, 40]，现在要将其转化为一个小顶堆。

首先，我们将数组按照完全二叉树的形式排列，如下图所示：

      10
     /  \
   20    15
  /  \
30   40

从上往下、从左往右依次给每个节点编号，如下所示：

      1
     / \
    2   3
   / \
  4   5

接下来，我们按照上述公式，依次确定每个节点在数组中的位置。例如，节点1的父节点下标为1/2=0，左子节点下标为2*1=2，右子节点下标为2*1+1=3，因此节点1在数组中的位置为0，节点2在数组中的位置为2，节点3在数组中的位置为3。

对应的数组为[10, 20, 15, 30, 40]，符合小顶堆的定义，即每个节点的值都小于或等于其子节点的值。