一、什么是堆

堆是一种拥有一下性质的完全二叉树——子节点的值总是大于（或小于）父节点的值

堆又可以分为大顶堆和小顶堆：

• 大顶堆：父节点的值永远大于其子节点的值，其中根节点的值最大
• 小顶堆：父节点的值永远小于其子节点的值，其中根节点的值最小

下面来看两个例子：

二、堆排序

所谓堆排序，就是利用堆的这一性质进行排序的算法，根据堆的不同，可以将堆排序分为有两种不同应用场合的堆排序算法：

• 大顶堆排序：适用于将数据排序成降序序列
• 小顶堆排序：适用于将数据排序成升序序列

而不论是大顶堆排序还是小顶堆排序，都无外乎进行一下三个步骤：

• 向下调整算法
• 建立堆算法
• 堆排序算法

我们一般采用数组结构来存储堆的值，下面主要来看一下小顶堆的操作过程，而大顶堆与之无异。

1. 向下调整算法

看了网上很多关于堆排序的文章，但是都没有介绍进行向下调整的意义何在，只是简单拍出了代码，但是这对于事后详细分析和初学而言非常不友好。

先来看一下怎么进行向下调整

• 使得当前节点满足最小堆的性质：父节点一定小于子节点的值。
  • 由于最小堆是一个递归定义：父节点一定小于子节点的值，其两个子节点同样如此，那么向下调整算法在上一步如果找到了违反规则的值，那么继续调整的时候，势必要从这个违反规则的子节点开始调整，递归进行，直到达到了最小堆的叶节点位置
  • 在调整的过程中，选择两个子节点中较大的那个，作为下次调整的节点
  • 如果两个子节点的较大值违反了规则吗，就交换其与父节点的之，并开始对这个较大的子节点进行同样的操作，直至达到叶节点

那么我们思考一下，调整的过程给了我们什么？

事实上是给出了一个从传入节点到叶节点的连续调整路径，所谓连续，就是只要路径走到符合规则的节点，就停止调整。那么经过本次调整后，本路径上的元素将达到有序。

那么只要能够使得多条路径覆盖所有节点，就一定可以完成堆的建立，而这就是建立堆的过程了。

2. 建立堆算法

既然上面都提到了向下调整的算法思想，那么建立堆的过程就需要实现路径全覆盖

既然堆是一个完全二叉树，那么堆的长度除以2，就是最后一个节点的父节点索引。

从倒数第二层查找到叶节点的调整路径、从倒数第三层查找经过倒数第二层到叶节点的调整路径、从倒数第四层查找经过倒数第三层、倒数第二层到叶节点的调整路径、。。。。。。。最终实现路径全覆盖。

3. 堆排序算法

经过建立堆算法，数组的元素的排列顺序已经可以满足堆的要求，但是并不是按升序排列的，需要进行交换调整。每次交换当前节点和根节点的值，重新进行向下调整，最终完成有序化

三、小顶堆排序算法

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
#define LEN 25
#define RANGE 20
template <class T>
void AdjustDown(T A[], int k, int len)
{
   
    auto i = k * 2 + 1;
    while (i <= len)
    {
   
        if (i < len && A[i] > A[i + 1])
            i++;
        if (A[k] > A[i])
        {
   
            swap(A[k], A[i]);
            k = i;
            i = i * 2 + 1;
        }
        else
            break;
    }
}
template <class T>
void BuildMinHeap(T A[], int len)
{
   
    for (auto i = len / 2; i >= 0; i--)
        AdjustDown(A, i, len);
}
template <class T>
void MinHeapSort(T A[], int len)
{
   
    BuildMinHeap(A, len);
    for (int i = len; i > 0; i--)
    {
   
        swap(A[i], A[0]);
        AdjustDown(A, 0, i - 1);
    }
}
template <class T>
void Output(T A[], int len)
{
   
    for (auto i = 0; i <= len; i++)
        cout << A[i] << " ";
    cout << endl;
}

int main()
{
   
    srand(time(0));
    int A[LEN];
    for (int i = 0; i < LEN; i++)
        A[i] = rand() % RANGE;
    Output(A, LEN - 1);
    MinHeapSort(A, LEN - 1);
    Output(A, LEN - 1);
    return 0;
}

四、大顶堆排序算法

相应地，我们得到大根堆排序的算法

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
const int LEN = 20;
const int RANGE = 10;
using namespace std;
template <class T>
void AdjustDown(T A[], int k, int len)
{
   
    auto i = 2 * k + 1;
    while (i <= len)
    {
   
        if (i < len && A[i] < A[i + 1])
            i++;
        if (A[k] < A[i])
        {
   
            swap(A[k], A[i]);
            k = i;
            i = i * 2 + 1;
        }
        else
            break;
    }
}
template <class T>
void BuildMaxHeap(T A[], int len)
{
   
    for (int i = len / 2; i >= 0; i--)
        AdjustDown(A, i, len);
}
template <class T>
void MaxHeapSort(T A[], int len)
{
   
    BuildMaxHeap(A, len);
    for (int i = len; i > 0; i--)
    {
   
        swap(A[i], A[0]);
        AdjustDown(A, 0, i - 1);
    }
}
template <class T>
void Output(T A[], int len)
{
   
    for (auto i = 0; i <= len; i++)
        cout << A[i] << " ";
    cout << endl;
}

int main()
{
   
    srand(time(0));
    int A[LEN];
    for (int i = 0; i < LEN; i++)
        A[i] = rand() % RANGE;
    Output(A, LEN - 1);
    MaxHeapSort(A, LEN - 1);
    Output(A, LEN - 1);
    return 0;
}

五、小顶堆运行结果

7 5 4 7 1 3 17 15 9 16 18 13 10 1 5 13 6 18 3 8 19 8 19 7 11
1 1 3 3 4 5 5 6 7 7 7 8 8 9 10 11 13 13 15 16 17 18 18 19 19