「数组」堆排序 / 大根堆优化（C++）
「数组」堆排序 / 大根堆优化（C++）
概述
在「数组」快速排序 / 随机值优化|小区间插入优化（C++）中，我们介绍了三种基本排序中的冒泡排序与分治思想结合的算法：快速排序。
本文我们来讲第二种基本排序：选择排序与分治思想结合的产物：堆排序。
我们来回想选择排序：每次选出最小的元素放在数组头部位置，每次都扫描一遍整个数组，整体表现为O(n²)。
我们希望只进行少量比较就能得出数组中的最小元素，该怎么做呢？堆这种结构给了我们一点启发。
核心概念：堆
堆是一颗完全二叉树，它的特点是可以用一维数组来储存。
堆结构
在初学数组排序阶段就理解二叉树似乎有些困难，不过好在我们不必完全了解二叉树的所有概念。
我们只需要知道：
①一个堆是一个层状结构，除去最底一层，每层的每个节点都有左子节点和右子节点，层层布满。
节点从上到下，从左到右依次编号。
（对于这样的结构，我们称之为二叉树，每个父节点都有左右孩子指针指向子节点。）
②只有最后一层允许节点不排满，但节点的排布仍然是严格从左到右的。
如下，图一和图二都是堆，但图三不是堆，因为它的最底层排布不是从左到右的。
③堆有两种：小根堆和大根堆。
小根堆要求父节点的值小于它的两个孩子，大根堆要求父节点的值大于它的两个孩子。
注意：一个节点的左右孩子之间的大小关系不做任何要求。
我们称二叉树的头结点为根，所以这种命名就很好理解了：小根堆的根最小，大根堆的根最大。
数组存堆
此时此刻我们完全不必知道二叉树的标准结构，因为数组就可以储存堆。
观察：
我们发现，一个序号从0开始的堆结构，
对于第idx个节点：
父节点序号：(idx-1)/2。
左子节点序号：idx*2+1。
右子节点序号：idx*2+2。
也就是说，对于上图这样的堆，我们将它存入数组应该是这样的：
i 0 1 2 3 4 5 6
int arr[i] 10 15 30 40 50 100 40
因此，对于一个堆，我们可以用数组来表示它。
思路
堆这种结构只是为我们的选择排序优化服务的。
选择排序需要我们每次找到最小的元素，那么我们不妨对数组建堆（又称堆化），获得一个小根堆数组后，堆顶，也就是序号为0的数组位置，自然就是我们要的最小元素。
获得最小元素后堆顶出堆，对剩余元素重新堆化，堆顶每次都是剩余元素中的最小元素。
我们不断进行堆顶出堆，就实现了选择排序。
考虑到堆化是按层实现的，因此若有n个元素，则有logn层，重新堆化的过程中内部重排最多进行logn次，通过logn次比较获得最小元素，这显然优于暴力选择排序。
算法过程
堆排序由两个操作构成：上浮up和下沉down。
我们先用宏定义描述一下节点父子关系，另有swap函数实现功能封装：
#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void swap(int& a, int& b) {
int temp = b;
b = a, a = temp;
}
up()
对数组进行初始堆化时，依靠上浮实现。
将堆的大小称为size，数组的整体长度称为len。
我们将数组arr分割成两部分：已经堆化的[0,size)，未堆化的剩余部分[size,len)
我们将剩余部分的第一个数加入堆中，它显然处于堆底，为了让它处于小根堆中合适的位置，我们进行对它上浮操作。
int size = 0;
for (int i = 0; i < len; i++) {
up(arr, i);
size++;
}
当idx为0时，不再上浮，否则判断此节点与其父亲的大小关系。
我们维护小根堆，所以如果父节点较大，则两者进行交换，使得父节点较小。
然后跟踪父节点，对父节点继续执行上浮操作。（这里的递归操作顺理成章的出现了）
void up(int arr[], int idx) {
if (idx && arr[father(idx)] > arr[idx]) {
swap(arr[father(idx)], arr[idx]);
up(arr, father(idx));
}
}
down()
数组完全堆化后，我们开始进行堆顶出堆，实现选择排序。
我们使用小根堆，因此需要一个额外的辅助空间来承载结果（后续它会被我们的优化方案优化掉）。
堆顶出堆后将堆中的最后一个元素赋给堆顶，堆size缩小，然后开始对堆顶执行下沉操作。
int* assist = new int[len];
for (int j = 0; j < len; j++) {
assist[j] = arr[0];
arr[0] = arr[--size];
down(arr,0,size);
}
memcpy(arr, assist, sizeof(int) * len);
delete[] assist;
定义pos，
①如果idx节点的左右孩子没有超出数组堆化范围，则pos等于左右孩子中较小的元素的索引，这是为了使得较小的元素总是位于堆的上部。
②如果idx的右孩子超出堆化范围，那么堆中只有左孩子是有效的，pos等于左孩子。
③如果idx的左孩子也超出堆化范围，说明idx已经在堆中沉底，没有后续元素，不必比较直接返回。
当pos位的元素小于idx位的元素时，两者作交换（即idx较大时，与其最小的子节点交换），然后跟踪pos，继续下沉。
void down(int arr[], int idx, int size) {
int pos;
if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);
else if (lchild(idx) < size)pos = lchild(idx);
else return;
if (arr[idx] > arr[pos]) {
swap(arr[idx], arr[pos]);
down(arr,pos,size);
}
}
Code
#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void up(int arr[], int idx) {
if (idx && arr[father(idx)] > arr[idx]) {
swap(arr[father(idx)], arr[idx]);
up(arr, father(idx));
}
}
void down(int arr[], int idx, int size) {
int pos;
if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);
else if (lchild(idx) < size)pos = lchild(idx);
else return;
if (arr[idx] > arr[pos]) {
swap(arr[idx], arr[pos]);
down(arr,pos,size);
}
}
void heap_sort(int arr[], int len) {
int size = 0;
for (int i = 0; i < len; i++) {
size++;
up(arr, i);
}
int* assist = new int[len];
for (int j = 0; j < len; j++) {
assist[j] = arr[0];
arr[0] = arr[--size];
down(arr,0,size);
}
memcpy(arr, assist, sizeof(int) * len);
delete[] assist;
}
优化方案
辅助数组assist看起来很愚蠢，我们来像个办法处理掉它。
大根堆优化
我们何不使用大跟堆来依次弹出数组的最大元素呢？
小根堆是从前往后进行最小值选择排序，因此无法安放在原始数组中（因为堆化部分会占据数组的前面部分），但大根堆解决了这个问题。
考虑到弹出时堆size收缩，因此数组的末尾会空出一个位置，我们可以直接将弹出元素安放到该位置上。
Code(pro)
#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void bigger_up(int arr[], int idx) {
if (idx && arr[father(idx)] < arr[idx]) {
swap(arr[father(idx)], arr[idx]);
bigger_up(arr, father(idx));
}
}
void smaller_down(int arr[], int idx, int size) {
int pos;
if (rchild(idx) < size)pos = arr[lchild(idx)] > arr[rchild(idx)] ? lchild(idx) : rchild(idx);
else if (lchild(idx) < size)pos = lchild(idx);
else return;
if (arr[idx] < arr[pos]) {
swap(arr[idx], arr[pos]);
smaller_down(arr, pos, size);
}
}
void HPsort(int arr[], int len) {
int size = 0;
for (int i = 0; i < len; i++,size++)
bigger_up(arr, i);
while (size--) {
swap(arr[0], arr[size]);
smaller_down(arr, 0, size);
}
}
注意：大根堆上浮大元素，沉底小元素。
复杂度
时间复杂度：O(nlogn)
空间复杂度：O(logn)
复杂度分析：
时间分析：{
考虑堆化是按层实现的，因此若有n个元素，则有logn层。
对n个元素建堆，每个元素按层上浮，最多比较logn次，得到O(nlogn)
对n个元素出堆，弹出堆顶后将堆尾赋给堆顶，每个元素按层下沉，最多比较logn次，得到O(nlogn)
O(nlogn)+O(nlogn)=O(2nlogn)=O(nlogn)。
}
空间分析：{
使用大跟堆建堆时，不使用额外空间承载答案。
建堆和出堆时调用递归函数进行压栈，函数最多调用logn层，最多占据空间O(logn)。
}
总结
堆为我们提供了一种新的视角来处理数组的最小元素，它的另一个重大用途就是实现优先队列priority_queue。
堆排序的分治策略也比较新颖：他不是在算法思想上进行分治，而是利用模拟堆这种数据结构进行分治，希望可以为你带来对分治思想的新启发。