关于堆-

今天讲的堆，简单记录一下：

堆，是一棵完全二叉树，因此设当前节点编号为 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 }

就先到这吧，再见啦！