堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

这是一个普通的堆，我们想把它变成最大堆，就必须了解最大堆的特点。然后我们对它进行调整，保证每个父节点的都大于孩子节点。

我们先调整这个二叉树的一部分，从它的最后一个节点开始调整，图中红色箭头开始调整，如果父节点小于孩子节点，就交换，否则结束。在看下一个节点，一直这样循环，直到全部调整完。

代码如下：

void_AdjustDown(size_tparent,size_tsize){size_tchild=2*parent+1;while(child<size){//child+1<size保证是最后一个节点if(child+1<size&&_arr[child]<_arr[child+1]){child++;//孩子节点最大的一个节点}//交换if(_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);parent=child;child=2*parent+1;}else{break;}}}

如果想把它调整成最小堆，必须符合每个父节点的都小于孩子节点，代码原理和最大堆相似。

代码如下：

void_AdjustUp(intchild){intparent=(child-1)/2;intsize=_arr.size();while(child>0){if(_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);child=parent;parent=(child-1)/2;}else{break;}}}

下面我给出完整代码，构造函数用的是调整成大堆。为了让代码更简洁，实现过程借用了库函数中的vector。

代码如下：

Heap.h中

#include<assert.h>#include<vector>template<classT>classHeap{public:Heap():_arr(NULL){}//构造函数Heap(constT*arr,size_tsize){_arr.reserve(size);for(size_ti=0;i<size;i++){_arr.push_back(arr[i]);}for(intj=(_arr.size()-2)/2;j>=0;j--){_AdjustDown(j,size);}}//拷贝构造Heap(constvector<T>&h){_arr.reserve(_arr.size());for(size_ti=0;i<_arr.size();i++){_arr.push_back(h[i]);}}//先储存在顺序表中，在进行下调voidpush(constT&x){_arr.push_back(x);_AdjustUp(_arr.size()-1);}//删除voidpop(){size_tsize=_arr.size();assert(size>0);swap(_arr[0],_arr[size-1]);//先把根结点和要删除的结点交换_arr.pop_back();//然后删除size=_arr.size();_AdjustDown(0,size);//最后上调}//堆是否为空boolEmpty(){size_tsize=_arr.size();assert(size>=0);returnsize==0;}//堆的大小size_tSize(){size_tsize=_arr.size();assert(size>=0);returnsize;}//访问根结点T&Top(){size_tsize=_arr.size();assert(size>0);return_arr[0];}voidPrint(){for(inti=0;i<Size();i++){cout<<_arr[i]<<"";}cout<<endl;}protected://下调void_AdjustDown(size_tparent,size_tsize){size_tchild=2*parent+1;while(child<size){//child+1<size保证是最后一个节点if(child+1<size&&_arr[child]<_arr[child+1]){child++;//孩子节点最大的一个节点}//交换if(_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);parent=child;child=2*parent+1;}else{break;}}}//上调void_AdjustUp(intchild){intparent=(child-1)/2;intsize=_arr.size();while(child>0){if(_arr[child]>_arr[parent]){swap(_arr[child],_arr[parent]);child=parent;parent=(child-1)/2;}else{break;}}}protected:vector<T>_arr;};

test.cpp中

#include<iostream>usingnamespacestd;#include"Heap.h"voidTest(){inta[]={10,16,18,12,11,13,15,17,14,19};Heap<int>h(a,sizeof(a)/sizeof(a[0]));h.Print();h.push(20);h.Print();h.pop();h.Print();Heap<int>h2(h);h2.Print();}intmain(){Test();system("pause");return0;}