LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法十三:树的应用之堆 - 从小到大和从大到小排列的问题

Clicks: 2513 Date: 2015-01-08 23:23:50 Power By 李轩Lane

算法

    

    堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。

    堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。

    如果一组数列,是无序的,要将它有序的排列,那么:

min = 9999;

for(i=0; i<n; i++){

    if(num[i] < min){

        min = num[i];

    }

}

    这是最简单也是最高效的算法。可是,如果现在要删除最小数,在数列中插入一个任意一个数,此时再求最小值呢?那么就要重复上面的操作。那么问题来了,如果这个动作要重复100亿次呢?此时,时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的,这个时候,我们引入了堆。

    最小堆的根节点永远是最小值!此时我们删掉了最小值,也就是根节点,在根节点的位置插入一个任意值,这个时候这个树就不是堆了,我们要把根节点向下移动,找到他合适的位置,也就是他要比他父节点大,比他的根节点小。此时这个树又恢复成了堆。

    现在有如下堆:

无标题.jpg


    堆的黑色数组表示节点的编号,在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。

    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:本算法参考《啊哈!算法》一书。

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号