堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。
堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。
如果一组数列,是无序的,要将它有序的排列,那么:
min = 9999; for(i=0; i<n; i++){ if(num[i] < min){ min = num[i]; } }
这是最简单也是最高效的算法。可是,如果现在要删除最小数,在数列中插入一个任意一个数,此时再求最小值呢?那么就要重复上面的操作。那么问题来了,如果这个动作要重复100亿次呢?此时,时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的,这个时候,我们引入了堆。
最小堆的根节点永远是最小值!此时我们删掉了最小值,也就是根节点,在根节点的位置插入一个任意值,这个时候这个树就不是堆了,我们要把根节点向下移动,找到他合适的位置,也就是他要比他父节点大,比他的根节点小。此时这个树又恢复成了堆。
现在有如下堆:
堆的黑色数组表示节点的编号,在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。
1、1号节点是根节点,永远是最小值,这是最小堆的特性。反之最大堆的根节点是最大值。
2、将1号节点的值改变为新插入的任意值。
3、将新插入的值向下移动,使树恢复为最小堆。和它的左子节点还有右子节点比较,若大,则交换位置。如此反复,直到不能再交换位置了。
使用最小堆来从小到大排列一个无序数列的全部代码如下,时间复杂度为O(NLogN):
#include <stdio.h> //存放堆 int h[100]; //存储堆的元素个数 int n; //交换元素 void swap(int x, int y){ int t; t = h[x]; h[x] = h[y]; h[y] = t; } //向下调整 void siftdown(int i){ int t, flag=0; //判断该点的做儿子是否存在 while(i*2 <= n && flag == 0){ //如果左儿子存在,则判断是否交换值 if(h[i] > h[i*2]) t = i * 2; else t = i; //右儿子是否存在 if(i*2+1 <= n && h[t] > h[i*2+1]){ t = i*2+1; } //如果需要交换则交换 if( t!= i){ swap(t, i); i = t; //如果不需要交换,则准备退出while }else{ flag = 1; } } } //向上调整,本函数本次将不会用到。 void siftup(int i){ int flag = 0; while(i != 1 && flag == 0){ if(h[i] < h[i/2]){ swap(i, i/2); i = i/2; }else{ flag = 1; } } } //创建堆 void create(){ int i; for(i=n/2; i>=1; i--){ siftdown(i); } } //获取最小的元素 int getMin(){ int t; //堆顶(根节点)为最小值 t = h[1]; //删除根节点,把堆的最后一个元素赋给根节点 h[1] = h[n]; n--; //把根节点向下移动,使堆恢复最小堆 siftdown(1); return t; } int main(){ int i, num; scanf("%d", &num); for(i=1; i<=num; i++){ scanf("%d", &h[i]); } n = num; //创建堆 create(); //讲堆从小到大排列 for(i=1; i<=num; i++){ printf("%d ", getMin()); } return 0; }输入
14 99 5 36 7 22 17 46 12 2 19 25 28 1 92输出
1 2 5 7 12 17 19 22 25 28 36 46 92 99
若使用最大堆,根节点就是整个数列的最大值,那么将h[1]和h[n]交换位置,此时h[n]就是最大值,然后将h[1]向下移动已恢复新的堆。此时将堆的大小减一,重复上面的操作。时间复杂度将会从O(NLogN)降低到O(NLogK)
完整代码如下:
#include <stdio.h> //存放堆 int h[100]; //存储堆的元素个数 int n; //交换元素 void swap(int x, int y){ int t; t = h[x]; h[x] = h[y]; h[y] = t; } //向下调整 void siftdown(int i){ int t, flag=0; //判断该点的做儿子是否存在 while(i*2 <= n && flag == 0){ //如果左儿子存在,则判断是否交换值 if(h[i] < h[i*2]) t = i * 2; else t = i; //右儿子是否存在 if(i*2+1 <= n && h[t] < h[i*2+1]){ t = i*2+1; } //如果需要交换则交换 if( t!= i){ swap(t, i); i = t; //如果不需要交换,则准备退出while }else{ flag = 1; } } } //创建堆 void create(){ int i; for(i=n/2; i>=1; i--){ siftdown(i); } } //从小到大排序 int minToMaxSort(){ while(n>1){ swap(1, n); n--; siftdown(1); } } int main(){ int i, num; scanf("%d", &num); for(i=1; i<=num; i++){ scanf("%d", &h[i]); } n = num; //创建堆 create(); //排序 minToMaxSort(); for(i=1; i<=num; i++){ printf("%d ", h[i]); } return 0; }输入
14 99 5 36 7 22 17 46 12 2 19 25 28 1 92输出
1 2 5 7 12 17 19 22 25 28 36 46 92 99Ps:本算法参考《啊哈!算法》一书。
友情提示:垃圾评论一律封号...