目录
概述
核心概念:堆
堆结构
数组存堆
思路
算法过程
up()
down()
Code
优化方案
大根堆优化
Code(pro)
复杂度
总结
概述
在「数组」快速排序 / 随机值优化|小区间插入优化(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。
堆排序的分治策略也比较新颖:他不是在算法思想上进行分治,而是利用模拟堆这种数据结构进行分治,希望可以为你带来对分治思想的新启发。