堆和堆排序


堆是一种优先队列的数据结构,本质是完全二叉树。根节点的值比所有节点的值都大,称为最大堆;根节点的值比所有节点的值都小,称为最小堆;在C++中可以用STL priority_queue或者STL heap实现。

最小堆的建堆以及堆排序如下:找一个满意的代码高亮好难啊

#include<iostream>
using namespace std;
int h[101]; //用来存放堆的数组
int n; //堆的元素个数
//从i节点向下调整堆
void siftdown(int i) //i为1即从堆顶开始调整
{
    int t, flag=0; //flag用于决定是否需要继续向下调整堆
        //当i节点有儿子(至少有左儿子的情况)并且需要调整的时候开始执行
    while(flag==0 && i*2<=n)
    {
                //判断它和左儿子的大小关系,用t来保存记录值较小的节点编号
        if(h[i] > 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(i!=t)
        {
            swap(h[t], h[i]); //交换这两个节点的值
            i = t; //更新需要调整的节点编号
        }
        else
        flag = 1; //说明当前父节点已经比子节点小了,不需要调整了
    }
    return;
}
//建立堆的函数
void creat()
{
        //从最后一个非叶节点开始向下调整
    for(int i=n/2; i>=1; i--)
    siftdown(i);
    return;
}
//删除堆顶元素,即存储堆中最小元素并删除
int deletmin()
{
    int t = h[1];
    h[1] = h[n];
    n--;
    siftdown(1); //每删除一个堆顶元素,开始从头调整
    return t;
}
int main(void)
{
    int num; //需要排序的个数
    cin>>num;
    for(int i=1; i<=num; i++)
    cin>>h[i];
    n = num;
    creat(); //建堆
    for(int i=1; i<=num; i++)
    cout<<deletmin()<<" "; //从小到大输出
    return 0;
}

当然堆排序还有一种更好的方法。从小到大排序的时候不建立最小堆而建立最大堆。最大堆建立好后,最大的元素在h[1]。因为我们的需求是从小到大排序,希望最大的放在最后。因此我们将h[1]和h[n]交换,此时h[n]就是数组中的最大的元素。请注意,交换后还需将h[1]向下调整以保持堆的特性。OK现在最大的元素已经归位,需要将堆的大小减1即n--,然后再将h[1]和h[n]交换,并将h[1]向下调整。如此反复,直到堆的大小变成1为止。此时数组h中的数就已经是排序好的了。
代码如下,注意使用这种方法来进行从小到大排序需要建立最大堆:

#include<iostream>
int h[101];//用来存放堆的数组
int n;//用来存储堆中元素的个数,也就是堆的大小
//向下调整函数
void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整
{
    int t, flag=0;//flag用来标记是否需要继续向下调整
    //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行
    while(i*2<=n && flag==0 )
    {        
        //首先判断他和他左儿子的关系,并用t记录值较大的结点编号
        if(h[i] < 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(h[t], h[i]);//交换它们,注意swap函数需要自己来写
            i = t;//更新i为刚才与它交换的儿子结点的编号,便于接下来继续向下调整
        }
        else
        flag = 1;//则否说明当前的父结点已经比两个子结点都要大了,不需要在进行调整了
    }
    return;
}
//建立堆的函数
void creat()
{
    int i;
    //从最后一个非叶结点到第1个结点依次进行向上调整
    for(i=n/2; i>=1; i--)
    siftdown(i); 
    return;
}
//堆排序
void heapsort()
{
    while(n>1)
    {
        swap(h[1], h[n]);
        n--;
        siftdown(1);
    }
    return;
}
int main(void)
{
    int i, num;
    cin>>num; //读入num个数
    for(i=1; i<=num; i++)
    cin>>h[i];
    n = num;   
    //建堆
    creat();
    //堆排序
    heapsort();
    for(i=1; i<=num; i++)
    cout<<h[i]<<" ";
    return 0;
}

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 堆和堆排序


Truth is I missed those summer days