详解堆排序
一、什么是堆
堆是一种拥有一下性质的完全二叉树——子节点的值总是大于（或小于）父节点的值
堆又可以分为大顶堆和小顶堆：
- 大顶堆：父节点的值永远大于其子节点的值，其中根节点的值最大
- 小顶堆：父节点的值永远小于其子节点的值，其中根节点的值最小
下面来看两个例子：
二、堆排序
所谓堆排序，就是利用堆的这一性质进行排序的算法，根据堆的不同，可以将堆排序分为有两种不同应用场合的堆排序算法：
- 大顶堆排序：适用于将数据排序成降序序列
- 小顶堆排序：适用于将数据排序成升序序列
而不论是大顶堆排序还是小顶堆排序，都无外乎进行一下三个步骤：
- 向下调整算法
- 建立堆算法
- 堆排序算法
我们一般采用数组结构来存储堆的值，下面主要来看一下小顶堆的操作过程，而大顶堆与之无异。
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
投递阿里云等公司8个岗位
