堆排序

 1 #include<iostream>
 2 using namespace std;
 3 int heap[101];
 4 int heap_size;
 5 void put(int d)                 //heap[1]为堆顶   插入 
 6 {
 7     int now, next;
 8     heap[++heap_size] = d;
 9     now = heap_size;
10     while(now > 1)
11     {
12         next = now/2;// 父节点 
13         if(heap[now] >= heap[next]) 
14         break;
15         swap(heap[now], heap[next]);
16         now = next;
17     }
18 }
19 int get()                //heap[1]为堆顶  获取 
20 {
21     int now=1, next, res= heap[1];
22     heap[1] = heap[heap_size--];//取出末尾元素 
23     while(now * 2 <= heap_size)
24     {
25         next = now * 2;// next 左孩子 
26         if (next < heap_size && heap[next + 1] < heap[next])
27         next++;
28         if (heap[now] <= heap[next]) 
29         break;
30         swap(heap[now], heap[next]);
31         now = next;
32     }
33     return res;
34 }
35 
36 int main()
37 {
38     int n;
39     cin>>n;
40     for(int i=1;i<=n;i++)
41     {
42         int dr;
43         cin>>dr;
44         put(dr);
45     }
46     for(int i=1;i<=n;i++)
47     {
48         cout<<get()<<endl;
49     }
50     return 0;
51 }

 stl

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 int a[10000001];
 6 int main()
 7 {
 8     int n;
 9     cin>>n;
10     for(int i=1;i<=n;i++)
11     {
12         //cin>>a[i];
13         scanf("%d",&a[i]);
14     }
15     make_heap(a+1,a+n+1);
16     sort_heap(a+1,a+n+1);
17     for(int i=1;i<=n;i++)
18     {
19         //cout<<a[i]<<endl;
20         printf("%d\n",a[i]);
21     }
22     return 0;
23 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P2792 [JSOI2008]小店购物(最小树形图)

    一开始的思路:新建一个虚点向每个点连边,再加上题面中给出的边,边权均为大小*需要购买的数量

    attack
  • 洛谷P4719 【模板】动态dp(ddp LCT)

    attack
  • cf113D. Museum(期望 高斯消元)

    设\(f[i][j]\)表示Petya在\(i\),\(Vasya\)在\(j\)的概率,我们要求的是\(f[i][i]\)

    attack
  • 【未完成】7-10 关于堆的判断 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 5-VI--ListView事件全解析

    张风捷特烈
  • Docker(16)- docker cp 命令详解

    小菠萝测试笔记
  • 双边过滤算法

         双边过滤算法作为一种改进的高斯过滤算法,在图像去噪,和均匀模糊(又称为磨皮),去锯齿效应上有不错的效果.双边过滤是采用Raised cosines函数...

    Gxjun
  • 优先队列

    glm233
  • C++拾趣——类构造函数的隐式转换

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csd...

    方亮
  • 复习C艹(更新中)

    之前在win7中运行c/c++下个vc就可以编译运行了,现在换了Mac,上网一看需要下个xcode,哎哟,好大啊,当时又没网,捉急,咦,mac的终端可以编译cp...

    仇诺伊

扫码关注云+社区

领取腾讯云代金券