网站开发要学多久,网站建设框架怎么做,保定网站设计制作,网站开通时间查询目录
概述
核心概念#xff1a;堆
堆结构
数组存堆
思路
算法过程
up()
down()
Code
优化方案
大根堆优化
Code(pro)
复杂度
总结 概述
在「数组」快速排序 / 随机值优化|小区间插入优化#xff08;C#xff09;中#xff0c;我们介绍了三种基本排序中的冒泡…目录
概述
核心概念堆
堆结构
数组存堆
思路
算法过程
up()
down()
Code
优化方案
大根堆优化
Code(pro)
复杂度
总结 概述
在「数组」快速排序 / 随机值优化|小区间插入优化C中我们介绍了三种基本排序中的冒泡排序与分治思想结合的算法快速排序。
本文我们来讲第二种基本排序选择排序与分治思想结合的产物堆排序。
我们来回想选择排序每次选出最小的元素放在数组头部位置每次都扫描一遍整个数组整体表现为O(n²)。
我们希望只进行少量比较就能得出数组中的最小元素该怎么做呢堆这种结构给了我们一点启发。 核心概念堆 堆是一颗完全二叉树它的特点是可以用一维数组来储存。 堆结构
在初学数组排序阶段就理解二叉树似乎有些困难不过好在我们不必完全了解二叉树的所有概念。
我们只需要知道
①一个堆是一个层状结构除去最底一层每层的每个节点都有左子节点和右子节点层层布满。
节点从上到下从左到右依次编号。
对于这样的结构我们称之为二叉树每个父节点都有左右孩子指针指向子节点。 ②只有最后一层允许节点不排满但节点的排布仍然是严格从左到右的。
如下图一和图二都是堆但图三不是堆因为它的最底层排布不是从左到右的。 ③堆有两种小根堆和大根堆。
小根堆要求父节点的值小于它的两个孩子大根堆要求父节点的值大于它的两个孩子。
我们称二叉树的头结点为根所以这种命名就很好理解了小根堆的根最小大根堆的根最大。
数组存堆
此时此刻我们完全不必知道二叉树的标准结构因为数组就可以储存堆。
观察 我们发现一个序号从0开始的堆结构
对于第idx个节点
父节点序号(idx-1)/2。
左子节点序号idx*21。
右子节点序号idx*22。
也就是说对于上图这样的堆我们将它存入数组应该是这样的 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*x1)
#define rchild(x) (2*x2)
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*x1)
#define rchild(x) (2*x2)
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*x1)
#define rchild(x) (2*x2)
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。
堆排序的分治策略也比较新颖他不是在算法思想上进行分治而是利用模拟堆这种数据结构进行分治希望可以为你带来对分治思想的新启发。
