三叉堆实现堆排序

佚名 6年前 (2019-04-11) 随笔 958人围观抢沙发百度已收录

 1 /*
 2 手写三叉堆 
 3 */
 4 #include<cstdio>
 5 #include<iostream>
 6 using namespace std;
 7 
 8 class heap3{
 9     private:
10         int heap[100001];
11         int heap_size;
12     public:
13         void put(int d);//类比二叉堆的put操作
14         int get();//类比二叉堆的get操作
15         int getsize();//返回当前堆的大小
16         void in(int x,int y);//因题目排序需要，写了这个函数，作用是将heap数组中的 第x个元素的值 赋值成y
17         void out(int n);//挨个访问 排序过的堆 中的元素
18 };
19 
20 heap3 m;
21 
22 void heap3::out(int n){
23     for(int k=1;k<=n;++k) cout<<heap[k]<<' ';
24 }
25 
26 void heap3::in(int x,int y){heap[x]=y;}
27 
28 void heap3::put(int d)
29 {
30     heap[++heap_size]=d;
31     int now=heap_size,next;
32     
33     while(now>1)
34     {
35         next=(now+1)/3;
36         if(heap[now]<=heap[next]) break;
37         swap(heap[now],heap[next]);
38         now=next;
39     }
40     
41     return;
42 }
43 
44 int heap3::getsize(){return heap_size;}
45 
46 int heap3::get(){
47     
48     int now=1,next;
49     int res=heap[1];
50     heap[1]=heap[heap_size--];
51     
52     while(now*3-1 <= heap_size)
53     {
54         next=now*3-1;
55         
56         if(next+1<=heap_size && heap[next+1]>heap[next]){
57             next++;
58             
59             if(next+1<=heap_size && heap[next+1]>heap[next]) next++;
60         }
61         else
62         if(next+2<=heap_size && heap[next+2]>heap[next]) next+=2;
63             
64         if(heap[now]>=heap[next]) break;
65         
66         swap(heap[now],heap[next]);
67         now=next;
68     }
69     return res;
70 }
71 
72 int main(){
73     int n,x;
74     scanf("%d",&n);
75     for(int i=1;i<=n;++i){
76         scanf("%d",&x);
77         m.put(x);
78     }
79     
80     for(int i=1;i<n;++i){
81         int k=m.getsize();
82         m.in(k,m.get());
83     }
84     
85     m.out(n);
86     
87     return 0;
88 }

关于三叉堆的资料，我是参考的这篇文章 http://www.docin.com/p-902813669.html

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

推荐大家读一下。

这篇文章表示：三叉堆比二叉堆更优秀

实际上确实是这样的，至少我经过实践，发现用三叉堆对 100000个数排序，比二叉堆快，

数据均为此题 https://www.luogu.org/problemnew/show/P1177 的数据。

由于是很久之前的代码了，解释都是现写的……

如图是一个三叉堆：

如果学习了二叉堆，理解三叉堆就变得很容易，因为原理都是一样的，解释都在注释里了，关于三叉堆，只有以下需要强调的了：

在数组中，每一个节点的父节点（除了根节点），都可以用当前节点的编号i，表示成（i+1）/3。

每一个节点的叶节点（如果有的话），可以按顺序表示成【i*3 - 1】、【i*3】、【i*3+1】。

类比二叉堆的 get 操作，读者需要注意一下这段代码，并思考一小下为什么，当时我卡了十几分钟……（其实还是我菜）

如下，是 get 操作中，选取当前节点最小（大）子节点的操作

1 if(next+1<=heap_size && heap[next+1]>heap[next]) {
2     next++;
3 
4     if(next+1<=heap_size && heap[next+1]>heap[next]) next++;
5 } else if(next+2<=heap_size && heap[next+2]>heap[next]) next+=2;