要說最大堆和最小堆，就得先知道最大樹和最小樹。
每個結點的值都大於（小於）或等於其子節點（如果有的話）值的樹，就叫最大（最小）樹。
最大堆（最小堆）是最大（最小）完全樹。
由於堆是完全二叉樹，所以可以用公式化描述，用一維數組來有效的描述堆結構。
利用二叉樹的性質：
如果對一棵有n個結點的完全二叉樹的結點按層序編號（從第1層到第[log2n]向下取整+1層，每層從左到右),則對任一結點i（1≤i≤n),有：
（1）如果i＝1，則結點i無雙親，是二叉樹的根；如果i>1，則其雙親是結點[i／2]向下取整。
（2）如果2i>n，則結點i為葉子結點，無左孩子；否則，其左孩子是結點2i。
（3）如果2i＋1>n，則結點i無右孩子；否則，其右孩子是結點2i＋1。
這樣就就可以將堆中結點移到它的父節點或者其中一個子節點處。
堆中進行的操作主要是：插入，刪除，以及初始化。
下面只討論最大堆。
在最大堆中進行插入操作，例如在下圖所示的左邊的最大堆中進行插入，插入後結構應該是和右邊的圖一樣的。
插入時，現將新元素從新堆的父節點開始比較，也就是先從2所在結點開始比較，如果小於父節點的值，那麼就直接作為孩子結點插入，如果大於，那麼就要現將父節點下移，然後再和父節點的父節點比較，一直比較到根節點為止，所以插入過程，是從葉節點到根的一條路徑。
最大堆的刪除，從最大堆的刪除時，該元素從根部移出。刪除後，此時堆需要重新構造，以便於仍然為完全二叉樹。例如下圖：
先將根節點的值20取出後，為了結構仍然是二叉樹，所以直接將最後一個結點，也就是保存2的結點去掉，然後將2的值保存下來，然後呢，就從根節點的兩個孩子開始比較，看看2 根的左右孩子，這三個元素中，誰最大，那麼根節點的值就是誰，然後就將2和空出來的結點的左右孩子(如果有的話)比較，確認子樹的根節點的值，這樣一步一步確認下去。
用數組初始化堆，數組元素顯示按照下面的順序，一個一個放在結點中
然後就從最後一個父節點開始，就是第五個結點，10所在的位置啦，從那裡開始構造以該節點為根的最大堆。構造好後就移到下一個結點，15所在結點，以此類推，一直到根節點。
下面是代碼：
文件"maxheap.h"
#include <iostream>
using namespace std;
template <class T>
class MaxHeap
{
private:
T *heap;
int CurSize;
int MaxSize;
public:
MaxHeap(int maxsize=10)
{
MaxSize=maxsize;
CurSize=0;
heap=new T[MaxSize+1];
}
~MaxHeap()
{
delete[]heap;
}
int Get_Size() const
{
return CurSize;
}
T Get_Max()
{
if(CurSize==0)
{
cout<<"堆為空"<<endl;
return -9999;
}
else
{
return heap[1];
}
}
MaxHeap<T> &Insert(const T& x)
{
if(CurSize==MaxSize)
{
cout<<"堆滿，"<<x<<" 插入失敗"<<endl;
return *this;
}
//為x尋找應插入位置
//i從新的葉子結點開始，沿著樹向上
int i=++CurSize;
while(i!=1 && x>heap[i/2])
{
heap[i]=heap[i/2]; //將元素下移
i/=2; //移向父節點
}
heap[i]=x;
cout<<x<<" 插入成功"<<endl;
return *this;
}
MaxHeap<T> &DeleteMax(T& x)
{
//將最大元素放入x，並從堆中刪除它
if(CurSize==0)
{
x=-9999;
return *this;
}
x=heap[1];
//重構堆
heap[0]=heap[CurSize--]; //0號位置存放最後一個元素值，然後將該位置刪除
//從根開始，為heap[0]尋找合適位置
int i=1;
int ci=2;
while(ci<=CurSize)
{
//ci是較大的孩子的位置
if(ci<CurSize && heap[ci]<heap[ci+1])
ci++;
//判斷是否可以放入heap[i]位置
if(heap[0]>heap[ci])
break;
//不能
heap[i]=heap[ci];
i=ci; // 下移一層
ci*=2;
}
heap[i]=heap[0];
return *this;
}
void Init_heap(T a[],int size,int maxsize)
{
delete[]heap;
heap=new T[maxsize+1];
CurSize=size;
MaxSize=maxsize;
for(int j=1;j<size+1;j++)
heap[j]=a[j];
//產生一個最大堆
for(int i=CurSize/2;i>=1;i--)
{
T y=heap[i]; //子樹的根
//尋找放置y的位置
int c=2*i;
while(c<=CurSize)
{
if(c<CurSize && heap[c]<heap[c+1])
c++;
if(y>=heap[c])
break;
heap[c/2]=heap[c];
c*=2;
}
heap[c/2]=y;
}
}
};
測試文件"main.cpp"
#include "maxheap.h"
#include <iostream>
using namespace std;
int main()
{
MaxHeap<int> hp;
int a[11]={-111,5,2,12,3,55,21,7,9,11,9};
cout<<"用數組a來初始化堆："<<endl;
for(int i=1;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;
hp.Init_heap(a,10,15);
int max;
cout<<"目前堆中最大值為："<<hp.Get_Max()<<endl;
hp.DeleteMax(max);
cout<<"刪除的堆中最大的元素為："<<max<<endl;
cout<<"刪除後，現在堆中最大的元素為："<<hp.Get_Max()<<endl;
cout<<"現在堆的大小為："<<hp.Get_Size()<<endl;
cout<<"向堆中插入新元素"<<endl;
hp.Insert(22);
hp.Insert(45);
hp.Insert(214);
hp.Insert(16);
hp.Insert(21);
hp.Insert(121);
hp.Insert(111);
cout<<"插入後現在堆的大小為："<<hp.Get_Size()<<endl;
cout<<"現在由大到小輸出堆中元素"<<endl;
do
{
hp.DeleteMax(max);
if(max== -9999)
break;
cout<<max<<" ";
}while(1);
cout<<endl;
return 0;
}
測試結果：
在只是需要使用一個優先隊列的時候，這種結構是十分有效率的，空間利用率也很高。但是並不適用於所有優先隊列的使用，尤其是需要合並兩個優先隊列或多個長度不相等的隊列的時候。
摘自：Kay's space Good Good Study,Day Day Up~
