飙血推荐
  • HTML教程
  • JavaScript基础教程
  • MySQL教程
  • JavaScript正则表达式运用
  • php入门教程
  • Excel函数教程
  • AngularJS教程
  • ThinkPHP5.0教程
  • UEditor使用文档

关于堆-

时间:2022-05-28  作者:zch061023  

今天讲的堆,简单记录一下:

堆,是一棵完全二叉树,因此设当前节点编号为 i,则其父结点编号为 i/2,左儿子编号为 2*i,右儿子编号为 2i+1

堆有两种比较特别:

一种是大根堆,一种是小根堆

由他们朴实的名字可知,大根堆就是每个节点都小于父亲节点的堆,小根堆反之。

关于堆的操作有两个比较常用的,一个是put(),另一个是get()。

put()算法介绍

put操作就是往堆里插入一个元素,我们如果硬插的话会有悖于堆的性质,所以要用能够维护堆的方法:

拿小根堆举例:在堆的末尾加入元素,并将该节点当成当前节点。然后比较当前节点与他的父亲的大小,如果当前节点小于其父节点。就将这两个节点位置互换,并持续此操作,直到当前节点不小于其父节点(等于不等于的都可以),以维护小根堆的性质,大根堆亦然。

代码如下:

 1 void put(int d)//展示的是小根堆的操作,大根堆亦然
 2 {
 3     int son,pa;
 4     heap[++heap_size]=d;
 5     son=heap_size;
 6     while(son>1)//到头了就不能继续了 
 7     {
 8         pa=son>>2;
 9         if(heap[son]>=heap[pa])//如果儿子本来就比他爹大,满足性质,直接break; 
10         {
11             break;
12         }
13         swap(heap[son],heap[pa]);//将爹与儿子进行交换 
14         son=pa;//让儿子的编号变成他爹的,再进行下一步操作 
15     }
16 }

当然,使用C++的标准模板库STL也是可以的:

1 #include<algorithm>//别忘了加STL的头文件 
2 void put(int d)
3 {
4     heap[++heap_size]=d;
5     push_heap(heap+1,heap+heap_size+1,greater<int>());//小根堆
6     push_heap(heap+1,heap+heap_size+1);//大根堆 
7 } 

get()算法介绍

put就是从堆中取出并删除元素的操作:

拿小根堆举例:

先将堆的根节点与堆尾元素互换,接着将对堆中元素的个数减1.

接着将当前的根节点视作pa比较他的两个儿子的大小(如果他有两个儿子)并选出较小的那个与父亲互换,一直持续此操作,直到又变成一个新的小根堆。大根堆亦然。

代码如下:

 1 int get()//This is 小根堆 
 2 {
 3     int pa,son,res;
 4     res=heap[1];//堆顶马上就要离开了,赶紧记录一下 
 5     heap[1]=heap[heap_size--];//先将堆顶的元素与堆尾的元素进行交换,再将堆中元素个数减一 
 6     pa=1;
 7     while(pa*2<=heap_size)//父亲是不能变成叶节点的欧 
 8     {
 9         son=pa*2;
10         if(son<heap_size && heap[son+1]<heap[son])//为了取最小的孩子 
11         {
12             son++;
13         }
14         if(heap[pa]<=heap[son]) break;
15         swap(heap[pa],heap[son]);
16         pa=son;
17     }
18     return res;
19 } 

还有就是C++标准模板库的STL:

1 #include<algorithm>
2 int get()
3 {
4     pop_heap(heap+1,heap+heap_size+1,greater<int>());//小根堆 
5     pop_heap(heap+1,heap+heap_size+1);//大根堆
6     return heap[heap_size--]; 
7 } 

我们由此可以将其运用起来:

1、堆排序:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 int heap_size,n;
 6 int heap[100001];
 7 void swap(int &a,int &b)
 8 {
 9     int t=a;
10     a=b;
11     b=t;
12 }
13 void put(int d)
14 {
15     heap[++heap_size]=d;
16     push_heap(heap+1,heap+heap_size+1,greater<int>());
17 }
18 int get()
19 {
20     pop_heap(heap+1,heap+heap_size+1,greater<int>());//小根堆 
21     return heap[heap_size--]; 
22 } 
23 int ans;
24 void work()
25 {
26     int x,y;
27     cin>>n;
28     for(int i=1;i<=n;i++)
29     {
30         cin>>x;
31         put(x);
32     }
33     for(int i=1;i<=n;i++)
34     {
35         cout<<get()<<\' \';
36     }
37 }
38 
39 int main()
40 {
41     work();
42     return 0;
43 }

2、合并果子

 其实就是将堆进行排序,将头两个元素相加成一个元素并放在堆尾,ans+=两数之和:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 int heap_size,n;
 6 int heap[100001];
 7 void swap(int &a,int &b)
 8 {
 9     int t=a;
10     a=b;
11     b=t;
12 }
13 void put(int d)
14 {
15     heap[++heap_size]=d;
16     push_heap(heap+1,heap+heap_size+1,greater<int>());
17 }
18 int get()
19 {
20     pop_heap(heap+1,heap+heap_size+1,greater<int>());//小根堆 
21     return heap[heap_size--]; 
22 } 
23 int ans;
24 void work()
25 {
26     int x,y;
27     cin>>n;
28     for(int i=1;i<=n;i++)
29     {
30         cin>>x;
31         put(x);
32     }
33     for(int i=1;i<n;i++)
34     {
35         x=get();
36         y=get();
37         ans+=x+y;
38         put(x+y);
39     }
40     cout<<ans;
41 }
42 
43 int main()
44 {
45     ios::sync_with_stdio(false);
46     work();
47     return 0;
48 }

就先到这吧,再见啦!

标签:编程
湘ICP备14001474号-3  投诉建议:234161800@qq.com   部分内容来源于网络,如有侵权,请联系删除。