HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-油漆面积-题解（C++代码）两种解法
浏览：650

蓝桥杯2013年第四届真题-核桃的数量-题解（C语言代码）
浏览：272

小白首选，简单易懂
浏览：247

你可能喜欢

数据结构-用数组实现堆排（易处理，容易理解）

　　作者: HzuQZH　　　　发表时间：2019-07-06 16:54:52 浏览：634　|　评论：0　

原题链接：数据结构-堆排序

堆其实是一根二叉树，他的顶点值永远小于等于他的左右儿子，这是小根堆，大根堆相反，在down（小根堆堆排）中，如果他存在左儿子并且左儿子比他小就交换他们的下标（因为是数组操作），右儿子也同理。最后再交换他们是值，再递归的去堆排每颗子树。
```cpp
    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef pair<int,int> P;
    typedef long long LL;
    namespace IO{
        inline LL read(){
            LL o=0,f=1;char c=getchar();
            while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
            while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
            return o*f;
        }
    }using namespace IO;
    const int N=1e5+7;
    int h[N],size;
    void down(int u){
        int t=u;
        if((u<<1)<=size&&h[u<<1]<h[t])t=(u<<1);//存在左儿子并且左儿子比他小
        if((u<<1|1)<=size&&h[u<<1|1]<h[t])t=(u<<1|1);//存在右儿子并且右儿子比他小
        if(u!=t){
            swap(h[u],h[t]);//与他的儿子中最小的数交换数值
            down(t);//递归的堆排子树
        }
    }
    int main(){
        int n,m;
        n=read();//快读（可scanf，可cin）
        for(int i=1;i<=n;i++)h[i]=read();
        size=n;
        for(int i=n/2;i;i--)down(i);（从n的一半开始堆排，可以降低复杂度）
        while(size){
		//因为这是小根堆，所以第一个是整个堆中最小的值，先输出最小的值，然后再用最后一个替换第一个值，再删除最后一个，再堆排，因为在数组中删除最后一个往往比删除第一个要容易
            printf("%d ",h[1]);
            h[1]=h[size--];
            down(1);
        }
        return 0;
    }
    
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-计负均正（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数据结构-用数组实现堆排（易处理，容易理解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

单词个数统计（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

母牛的故事（java语言代码）

C语言训练-求PI* （C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

数据结构-用数组实现堆排（易处理，容易理解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

单词个数统计 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

母牛的故事 （java语言代码）

C语言训练-求PI* （C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

【亲和数】（C语言代码）

单词个数统计（C语言代码）

母牛的故事（java语言代码）