算法与数据结构之最大/最小堆
这里涉及到了堆结构，作为引入，要先讲讲一种特殊的树结构——完全二叉树
完全二叉树
完全二叉树就是像下图一样的二叉树，所有叶结点的深度相同，并且所有内部结点都有两个子结点
看这个图就很好理解什么叫完全二叉树了。真的很完美啊哈哈哈。
但是，有另外一种树结构也叫做完全二叉树。准确来说就是近似是完全二叉树。
长这样子：
上面这种二叉树，叶节点的深度的最大差距是1，最下层叶节点都集中分布在这层最左边的若干位置上，那么这种二叉树我们也可以把它叫做完全二叉树。
二叉堆
上面这种类型的数据结构我们将它称为二叉堆。二叉堆在逻辑上虽然是完全二叉树，但是它却是以1为起点的一维数组表示的。假设表示二叉堆的数组为A，二叉堆的大小（元素的数量）为H，那么二叉堆的元素就存储在 A[1, … , H] 中，其中根的下标是1.观察可以发现，只要一个结点的下标i确定了，那么它的父节点就是floor(i/2)，左子结点下标是2*i, 右子结点的下标是2*i+1。
二叉堆和完全二叉树的区别之一在于，二叉堆中存储的各结点的键值需要保证堆具有以下性质之一
·最大堆性质： 结点的键值都小于等于其父结点的键值。
·最小堆性质： 结点的键值都大于等于其父结点的键值。
满足最大堆性质的二叉堆叫做最大堆，满足最小堆性质的二叉堆叫做最小堆。
最大堆的根结点中存储着最大的元素，最小堆的根结点中存储着最小的元素。
需要注意的是，二叉堆中只有父子结点之间有大小关系的限制，而兄弟结点之间并没有大小关系的限制。
应用二叉堆这种数据结构，我们就可以在保持数据大小关系的前提下，有效地取出优先级最高的元素，或者添加新的元素。
构建完全二叉树
下面要实现一个程序，读取以完全二叉树形式表示的二叉堆。注意，这里只是构建一棵完全二叉树，并不需要这个树满足二叉堆的规则。
输入两行数据，第一行是元素的个数
第二行是各个结点的值。
要求按结点id顺次输出结点的父结点、左子结点、右子结点的值。如果这些结点不存在，那么就不用输出。
题目出自
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_A
题目编号是 ALDS1_9_A
样例输入
5
7 8 1 2 3样例输出
node 1: key = 7, left key = 8, right key = 1,
node 2: key = 8, parent key = 7, left key = 2, right key = 3,
node 3: key = 1, parent key = 7,
node 4: key = 2, parent key = 8,
node 5: key = 3, parent key = 8, 这道题我们只需要根据完全二叉树的定义，就能生成这棵完全二叉树。
完全二叉树的代码实现
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int main()
{
long long nd[260];
int h;
cin>>h;
for(int i=1;i<=h;i++)
{
cin>>nd[i];
}
for(int i=1;i<=h;i++)
{
printf("node %d: key = %lld, ",i, nd[i]);
if(floor(i/2)!=0)
printf("parent key = %lld, ", nd[int(floor(i/2))]);
if(2*i<=h)
printf("left key = %lld, ", nd[2*i]);
if(2*i+1<=h)
printf("right key = %lld, ", nd[2*i+1]);
cout<<endl;
}
}最大堆
有了上面生成完全二叉树的基础，我们就能根据最大堆的性质来生成最大堆。
最大堆的生成有一个叫做堆化的过程，在这个过程中，利用自己写的一个max_Heapify函数，使得 A[i] 的值一致向叶结点方向移动，直至它找到合适的位置。这个过程能通过递归来实现。
但是如果从完全二叉树的根入手来解决这个问题的话，就会发现整个操作变得异常的复杂。
所以，我们可以从叶结点来入手解决这个问题。
首先，我们会发现叶结点由于没有子结点，根本不需要向下进行任何的对换操作。那么我们就直接研究叶结点的父结点就好了。
由于完全二叉树每一层的结点数量最大是上一层的两倍，所以，我们只需要从结点id为H/2的结点开始，终点是结点id=1的结点，都进行一遍max_Heapify就可以生成最大堆了。
每次执行max_Heapify的时候，当前结点i的左右子树都已经是最大堆了，所以，我们只需要关注当前结点该移动到哪个位置而已。
生成最大堆的代码实现
题目来源：
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
在这个程序中，输入数据的格式和上一题一样
我们要实现把一棵完全二叉树变成一个最大堆。那就按照上面的思路，从叶结点入手，自下而上的处理
#include<iostream>
using namespace std;
long long nd[500009];
int h;
void max_Heapify(int i)
{
int l = 2*i;
int r = 2*i+1;
//从左子结点、自身、右子结点中选出值最大的结点
int largest = i;
if(l<=h&&nd[l]>nd[largest])
largest = l;
if(r<=h&&nd[r]>nd[largest])
largest = r;
if(largest!=i)
{
swap(nd[i], nd[largest]);
max_Heapify(largest);
}
}
int main()
{
cin>>h;
for(int i=1;i<=h;i++)
{
cin>>nd[i];
}
for(int i=h/2;i>=1;i--)
max_Heapify(i);
for(int i=1;i<=h;i++)
cout<<" "<<nd[i];
cout<<endl;
}生成最小堆
我们只需要把上面的生成最大堆的代码稍加修改，就能改成生成最小堆的代码。
只要把max_Heapify函数改成下面的min_Heapify函数就可以了。其实就是改变了交换元素的规则。
void min_Heapify(int i)
{
int l = 2*i;
int r = 2*i+1;
//从左子结点、自身、右子结点中选出值最小的结点
int smallest = i;
if(l<=h&&nd[l]<nd[smallest])
smallest = l;
if(r<=h&&nd[r]<nd[smallest])
smallest = r;
if(smallest!=i)
{
swap(nd[i], nd[smallest]);
min_Heapify(smallest);
}
}腾讯云开发者
