堆的实现（数据结构）
一、问题描述
堆是什么？堆也叫做优先队列，一些按照重要性或优先级来组织的对象称为优先队列。
为什么需要堆？在现实生活中，存在许多需要从一群人、一些任务或一些对象中找出“下一位最重要”目标的情况。例如：在平时处理事情的时候我们总会先把“下一个最重要的”的事情取出来先处理。在处理的过程中，可能还会有其他的事情加进来。因此在事情处理完的事情，我们又要重新找出“下一个最重要”的事情进行处理。
如何去建立一个堆？通常来说，我们容易想到以下的方法：
A、对所有元素进行一次排序然后取出最大值。但这种方法不是很好。它多做了很多无用功。因为其实我可能只要取一个最大值就OK了，但是却画蛇添足地帮我把所有元素都排好序了。很浪费时间。排序的时间复杂度至少为O(nlogn),插入和删除操作的时间复杂度为O(n)。理论上我们所要实现的优先队列的时间复杂度是可以比这个更优的。
因此就出现了堆。
定义：
1.它是一棵满二叉树，所以往往用数组来实现这棵二叉树。
2.堆中的数据是局部有序的。也就是节点储存的值和它的子节点之间存在某种关系。
结构图：
堆类型：
最大值堆的性质：任意一个节点的值都大于它的子节点的值；这样子根节点存储的就是这组数据的最大值。
（以上图为例，A的值必须要大于B和C的值，B的值必须要大于D和E的值，但是C和D之间以及C和E之间没有必然的大小关系。C可以比D大也可以比D小）
最小值堆的性质：任意一个节点的值都小于它的子节点的值；这样子根节点存储的就是这组数据的最小值。
注意点：堆的兄弟节点之间没有必然的联系
我们以最大值堆为例，来看一下它的结构示例图：
接下来我们来实现一个最大值堆。
二、详细设计
（一）、首先我们需要构建一个堆类。
1、这个类需要包含以下的属性和方法
A、属性：指向堆数组的指针、堆的最大元素个数、当前堆的元素个数
B、方法：
构造函数（设置初始值）
返回当前元素个数
判断当前节点是否是叶节点
返回当前节点的左孩子节点位置
返回当前节点的右孩子节点位置
返回当前节点的父节点位置
建堆函数
下拉函数
插入函数
移除函数
（二）、算法思想
1、判断当前函数是否是叶节点
由于我们的树是存放在数组中的，我们可以通过下标来判断。如果下标的值大于等于n/2并且小于n，就说明它是一个叶节点。
2、返回左右孩子及父节点的位置
我们可以通过当前节点的下标来计算。
完全二叉树在数组中的储存如下：
|
P1 |
LC1 |
RC1 |
|
|
|
|
根据二叉树的结构和数组下标的信息，我们可以推断出一下结论：
左孩子节点：2*pos+1;
右孩子节点：2*pos+2；
父节点：(pos-1)/2；
3、建堆函数
有两种方法，一种是利用插入函数，逐个插入数据。另一种是对已经存有数据的数组进行堆排序。我们这里采用的是第二种方法。基本思路：依次从树的倒数第二层往上遍历节点。如果当前节点的值小于它的某一个叶节点，我们调用下拉函数进行下拉操作。而由于叶节点不可能再往下走，所以我们直接从倒数第二层开始遍历即可。倒数第二层的位置：n/2-1。
4、下拉函数
判断当前节点和它两个子节点的大小关系，如果当前节点小于它的子节点。那么就将该节点往下拉。与较大的子节点交换位置。
5、插入函数
首先将要插入的数据加到堆的一个叶节点中，也就是当前数组的尾部。然后判断该节点和其父节点的大小关系，如果该节点大于其父节点，就把其上拉，和父节点交换位置，重复该过程直到该节点到了正确的位置。
6、移除函数
先把根节点和最后一个叶节点交换位置，把堆的元素大小减1。对改变后的根节点进行下拉操作，直到正确的位置。最后再返回被替换的那个叶节点的值。
（三）、源码分析
C++版代码+运行结果
#include<iostream>
using namespace std;
template<class E>
void swap(E *Heap,int p,int j){
E zj=Heap[p];
Heap[p]=Heap[j];
Heap[j]=zj;
}
//Heap class
template<class E>
class heap{
private:
E *Heap;//指向Heap数组的指针
int maxsize;//堆的最大空间
int n;//堆的当前元素个数
//下拉函数
void siftdown(int pos){
while(!isLeaf(pos)){//如果已经拉到叶节点了就停止
int j=leftchild(pos);
int rc=rightchild(pos);//获取左右孩子节点的pos
if((rc<n)&&(Heap[rc]>Heap[j]))
j=rc;//把j指向较大的子节点的位置
if(Heap[pos]>Heap[j]) return;
swap(Heap,pos,j);//如果根节点的值大于较大的子节点的值，就交换位置
pos=j;//继续往原本值较大的节点走
}
}
public:
//创建构造函数
heap(E *h,int num,int max){
Heap=h; n=num; maxsize=max; buildHeap();
}
//返回当前堆的大小
int size() const{ return n;}
//判断当前节点是否是叶节点
bool isLeaf(int pos) const{ return (pos >= n/2) && (pos<n);}
//返回左孩子节点的位置
int leftchild(int pos) const{ return 2*pos + 1;}
//返回右孩子节点的位置
int rightchild(int pos) const{ return 2*pos + 2;}
//返回父母节点的位置
int parent(int pos) const{ return (pos-1)/2;}
//建堆函数
void buildHeap() {
for(int i=n/2-1;i>=0;i--) siftdown(i);//从倒数第二层开始往上遍历，依次调用下拉函数，建立最大值堆
}
//构建插入函数
void insert(const E it){
if(n>=maxsize){
cout<<"Heap is full!"<<endl;
return;
}
int curr = n++;//开辟一个位置
Heap[curr]=it;//在数组的最后加入数据
//加入之后开始将这个值往上拉
while((curr!=0)&&(Heap[curr]>Heap[parent(curr)])){
swap(Heap,curr,parent(curr));
curr = parent(curr);//往上走
}
}
//移除首个元素，也就是最大值
E removefirst(){
if(n<=0){
cout<<"Heap is empty!"<<endl;
return 0;
}
swap(Heap,0,--n);//把最后一个元素和第一个元素换位置,将堆的空间减1
if(n!=0) siftdown(0);//如果堆元素不为0,就对该元素进行下拉操作直到合适的位置
return Heap[n];//返回最大值
}
};
int main(){
int n,maxsize=256;
cin>>n;
int h[n];
for(int i=0;i<n;i++) cin>>h[i];
heap<int>a(h,n,maxsize);//数据类型属于模板的对象实例化要带上具体的数据类型
//检测建堆函数
for(int i=0;i<n;i++){
cout<<h[i]<<" ";
}
cout<<endl;
//检测出堆函数
int max=a.removefirst();
cout<<max<<endl;
for(int i=0;i<n;i++){
cout<<h[i]<<" ";
}
cout<<endl;
//检测插入函数
a.insert(15);
for(int i=0;i<n;i++){
cout<<h[i]<<" ";
}
cout<<endl;
return 0;
}
/*
8
5 3 21 6 9 4 5 12
*/Java版代码+运行结果
package version2;
public class Node {
public int key;//关键字，也就是权值
public String value;//值
public Node(int key,String value){
this.key=key;
this.value=value;
}
}
package version2;
import java.util.ArrayList;
public class Heap {
public ArrayList<Node>nodeList;//存储数据的数组，可以说就是堆
private int length;//堆的大小
public Heap(){
}
public Heap(ArrayList<Node>nodeList){
this.nodeList=nodeList;
this.length=nodeList.size();
}
//交换函数，交换两个节点的位置
public void swap(Node nodeA,Node nodeB){
Node nodetemp=new Node(nodeA.key,nodeA.value);
nodeA.key=nodeB.key;
nodeA.value=nodeB.value;
nodeB.key=nodetemp.key;
nodeB.value=nodetemp.value;
}
public int length(){
return length;
}
//判断是不是叶节点
public boolean isLeaf(int pos){
return (pos >= length/2) && (pos<length);
}
//返回左孩子节点的地址
public int leftchild(int pos){
return 2*pos+1;
}
//返回右孩子节点的地址
public int rightchild(int pos){
return 2*pos+2;
}
//返回父节点的地址
public int parent(int pos){
return (pos-1)/2;
}
//建堆函数
public void buildHeap(){
for(int i=length/2-1;i>=0;i--) shiftDown(i);//从倒数第二层开始往上遍历，依次调用下拉函数，建立最大值堆
}
//下拉函数
public void shiftDown(int pos){
while(!isLeaf(pos)){//如果已经拉到叶节点了就停止
int j=leftchild(pos);
int rc=rightchild(pos);//获取左右孩子节点的pos
if((rc<length)&&(nodeList.get(rc).key>nodeList.get(j).key))
j=rc;//把j指向较大的子节点的位置
if(nodeList.get(pos).key>nodeList.get(j).key) return;
swap(nodeList.get(pos),nodeList.get(j));//如果根节点的值大于较大的子节点的值，就交换位置
pos=j;//继续往原本值较大的节点走
}
}
//插入新节点
public void insert(Node node){
nodeList.add(node);
int curr=nodeList.size()-1;//新插入数据的位置
//加入之后开始将这个值往上拉
while((curr!=0)&&(nodeList.get(curr).key>nodeList.get(parent(curr)).key)){
swap(nodeList.get(curr),nodeList.get(parent(curr)));
curr = parent(curr);//往上走
}
length++;//数量加1
}
//取最值函数
public Node removeFirst(){
if(length<=0){
System.out.println("Heap is empty!");
return null;
}
swap(nodeList.get(0),nodeList.get(--length));//把最后一个元素和第一个元素换位置,将堆的空间减1
if(length!=0) shiftDown(0);//如果堆元素不为0,就对该元素进行下拉操作直到合适的位置
return nodeList.get(length);//返回最大值
}
public static void main(String[] args) {
ArrayList<Node>nodeList=new ArrayList();
nodeList.add(new Node(1,"A"));
nodeList.add(new Node(2,"B"));
nodeList.add(new Node(3,"C"));
nodeList.add(new Node(4,"D"));
Heap heap=new Heap(nodeList);
System.out.println("当前的数组结构");
for(int i=0;i<heap.length();i++){
System.out.println(heap.nodeList.get(i).key+"-"+heap.nodeList.get(i).value);
}
heap.buildHeap();
System.out.println("当前的堆结构");
for(int i=0;i<heap.length();i++){
System.out.println(heap.nodeList.get(i).key+"-"+heap.nodeList.get(i).value);
}
Node result=heap.removeFirst();
System.out.println("最大值:"+result.key+result.value);
result=heap.removeFirst();
System.out.println("最大值:"+result.key+result.value);
}
}
至此我们已经成功构建了最大值堆。最小值堆只需要做一些小修改即可。
上一篇： 【C语言】汉诺塔问题（递归）