[数据结构]“堆”是一个很神奇的东西(复杂版)

啊哈磊

[code=Cpp width=740px]// Author: Ahalei
// Date: 11 6, 2010
// City: Wuhan
// Website: www.ahalei.com
// Title: Heap(最大堆)

#include <stdio.h>
int h[101];//用来存放堆的数组
int n;//用来存储堆中元素的个数，也就是堆的大小
//交换函数，用来交换堆中的两个元素的值
void swap(int x,int y)
{
    int t;
    t=h[x];
    h[x]=h[y];
    h[y]=t;
}
//求最大值函数，用来返回a和b中较大的一个
int max(int a,int b)
{
    return a>b?a:b;//这是一个三目运算符，如何使用请问baidu
}
//向上调整函数
void siftup(int i)
{
    int flag=0;//用来标记是否仍然需要继续调整
    //如果是堆顶，就返回，不需要调整了
    if(i==1)
        return;
    //不在堆顶 并且 他比爸爸大的时候 继续调整
    while(i!=1 && flag==0)
    {
        //看看他的是否比他的爸爸大
        if(h>h[i/2])
            swap(i,i/2);//交换他和他爸爸的位置
        else
            flag=1;//表示当前已经不需要调整了，已经符合堆得结构，他比他爸爸小了
        i=i/2;//这句话很重要，对他的爸爸继续进行调整
    }
}
//向下调整函数
void siftdown()
{
    int flag=0,t,i;//用来标记是否仍然需要继续调整
    //堆的顶点开始向下调整
    i=1;
    //当他至少有左儿子的时候 并且仍然 有需要继续调整的时候循环
    while( 2*i<=n && flag==0)
    {
        //首先判断他和他左儿子的关系
        if( h < h[i*2] )
            t=i*2;//记录值较大的节点编号
        else
            t=i;//记录值较大的节点编号
        //如果他有右儿子的情况下，再对右儿子进行讨论
        if(i*2+1 <= n)
        {
            //首先判断他和他右儿子的关系
            if(h[t] < h[i*2+1])
                t=i*2+1;//记录值较大的节点编号
        }
        //如果最大的节点编号不是自己，也就是说他的孩子中有比他大的  
        if(t!=i)
        {
            swap(t,i);//交换他们
            i=t;//更新i为他的孩子的编号，继续向下调整
        }
        else
            flag=1;//则否说明当前的爸爸已经比两个孩子都要大了，不需要在进行调整了
    }
}
//建立堆的函数
void creat()
{
    int i;
    //从最后一个节点到第一个节点进行向上调整
    for(i=n;i>=1;i--)
    {
        siftup(i);
    }  
}
//删除最大的元素
int deletemax()
{
    int t;
    t=h[1];//用一个临时变量记录堆顶点的值
    h[1]=h[n];//将堆得最后一个点赋值到堆顶
    n--;//堆的元素减少1
    siftdown();//向下调整
    return t;//返回之前记录的堆得顶点的最大值
}
int main()
{
    int i,num;
    //读入n个数
    scanf("%d",&num);
    n=num;
    for(i=1;i<=num;i++)
        scanf("%d",&h);   
    //建堆
    creat();
    //删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来
    for(i=1;i<=num;i++)
        printf("%d ",deletemax());
   
    getchar();
    getchar();
    return 0;
}
</stdio.h>[/code]

第十五撒旦就奥

哇，这是啥，好神奇，好复杂啊

嗨，强哥！

虽然看不懂，但是学习了程序的书写格式。尤其是注释要足够“二”，哈哈

981013

堆是一个完全二叉树（除最后一层外，其他各层节点数都达到最大个数，且底层各节点从左至右连续排列的二叉树），且该树中每个父节点的数据大于等于（或小于等于，看要求）各子节点数据。
堆可以用来排序，堆排序是排序方法中较为快速的一种，平均与最坏情况下复杂度皆为O(nlogn)
（资料来源《零基础学算法》【机械工业出版社】）

shock

981013 发表于 2013-8-14 12:57
堆是一个完全二叉树（除最后一层外，其他各层节点数都达到最大个数，且底层各节点从左至右连续排列的二叉树 ...

堆不一定是二叉树

超神级

这难道这就是程序猿的书写格式！
这个注释太那个了！
注释比代码还要多！！