堆排序

2018-06-17 22:56:48来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 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 } 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:3143 二叉树的序遍历

下一篇:C++ 遍历可变模板参数 iterate variadic template arguments