算法十三:树的应用之堆 - 从小到大和从大到小排列的问题
堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。
堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。
如果一组数列,是无序的,要将它有序的排列,那么:
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 99
Ps:本算法参考《啊哈!算法》一书。