【数据结构】【堆排序】

前端之家收集整理的这篇文章主要介绍了【数据结构】【堆排序】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

这里是先建立最大堆,再从小到大输出堆元素。具体实现及其解释见代码

总结:像这样支持插入元素和寻找最大(小)值元素的数据结构称为优先队列。堆就是优先队列的实现,很大程度的降低了时间复杂度。

另外Dijkstra算法每次找离源点最近的一个顶点也可以用堆来优化,使算法复杂度降到O((m+n)logn).具体实现见我另一篇博客堆排序实现dijsktra

用堆排序来优化prime算法见博客堆排序优化的prime算法

#include<stdio.h>

int h[1000],n;//h是存放堆的数组,n存放堆的结点个数 
void swap(int x,int y)//交换函数 
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
}
void siftdown(int a)//向下调整函数 
{//传入一个需要向下调整的结点编号a,这里传入1,即从堆的顶点开始向下调整 
    int t,flag = 0;//flag用来标记是否需要继续向下调整 
    while(a*2 <= n&&!flag)
    {//当前结点至少得有左子结点 
        if(h[a] < h[a*2])//判断a和左子结点的关系,t记录较大结点 
            t = a*2;
        else
            t = a;
        if(a*2+1 <= n)//如果它有右子结点,再对右子结点进行讨论 
        {
            if(h[t] < h[a*2+1])
                t = a*2+1;
        }
        if(t!=a)//如果最大结点编号不是自己,说明子结点中有比父结点更大的 
        {
            swap(t,a);//交换他们,swap函数自己定义 
            a = t;//a更新为最大结点编号,方便继续向下调整 
        }
        else
            flag = 1;//最大结点编号是自己,则不需要继续向下调整 
    }
    return;
}
void creat()//建立堆函数 
{
    int i;
    for(i = n/2; i >= 1; i --)//从最后一个非叶结点到第一个结点依次向上调整 
        siftdown(i);
    return;
}
void heapsort()//堆排序 
{
    while(n>0)
    {
        swap(1,n);
        n--;
        siftdown(1);
    }
    return;
}
int main()
{
    int num,i;
    while(scanf("%d",&num)!=EOF)
    {
        for(i  =1; i <= num; i ++)
            scanf("%d",&h[i]);
        n = num;
        creat();//建堆 
        heapsort();//堆排序 
        for(i = 1; i <= num; i ++)//输出 
            printf("%d ",h[i]);
            printf("\n");
    }
    return 0;
}
原文链接:https://www.f2er.com/datastructure/382297.html

猜你在找的数据结构相关文章