一、何為“堆”
（一）基本概念
1、滿二叉樹
?一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為k，且結(jié)點總數(shù)是(2k) -1 ，則它就是滿二叉樹。如下圖所示例子：
2、完全二叉樹
?完全二叉樹的結(jié)點數(shù)是任意的，從形式上講它是個缺失的的三角形，但所缺失的部分一定是右下角某個連續(xù)的部分，最后那一行可能不是完整的，對于k層的完全二叉樹，結(jié)點數(shù)的范圍2(k-1)-1 < N< 2k – 1；
?設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。如下圖所示例子：
?有關(guān)二叉樹的知識，小編并沒有很系統(tǒng)的去總結(jié)，接下來也將做一個深入分享。
（二）堆的定義及其分類
1、 定義
?堆（英語：heap)是計算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，是一顆完全二叉樹，通常是一個可以被看做一棵樹的數(shù)組對象。
?堆是具有以下性質(zhì)的完全二叉樹：
?（1）每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆；
?（2）每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。
2、二叉堆的分類
（1）大頂堆
?大頂堆中，每個結(jié)點的值都大于其左孩子和右孩子結(jié)點的值。我們來畫個圖演示下：
（2）小頂堆
?小頂堆中，每個結(jié)點的值都小于其左孩子和右孩子結(jié)點的值。同樣給個例子如下：
（三）堆結(jié)點訪問
?通常堆是通過一維數(shù)組來實現(xiàn)的。在數(shù)組起始位置為0的情形中，父結(jié)點和子結(jié)點的位置關(guān)系如下：
?（1）索引為i的左孩子的索引是 (2* i+1)
?（2）索引為i的右孩子的索引是 (2* i+2)
?（3）索引為i的父結(jié)點的索引是 (i -1)/2
?注意：這里得到的關(guān)系由數(shù)組的起始位置來決定。小伙伴們可以對照上述大頂堆和小頂堆的圖來分析分析索引的對應(yīng)關(guān)系。
?因此，在第一個元素的索引為0時：
?對于大頂堆有：arr(i)>arr(2* i+1) && arr(i)>arr(2* i+2)
?對于小頂堆有：arr(i)<arr(2* i+1) && arr(i)<arr(2* i+2)
二、構(gòu)造初始堆（堆調(diào)整）
?將無序數(shù)組構(gòu)造成一個堆（升序用大頂堆，降序用小頂堆）。假設(shè)存在以下數(shù)組：
?首先，我們找到當(dāng)前這棵樹的最后一個非葉子結(jié)點，對從該結(jié)點開始的所有非葉子結(jié)點進(jìn)行結(jié)構(gòu)判斷，并依次進(jìn)行調(diào)整。注意，這里是自底向上，從右至左對非葉子結(jié)點進(jìn)行判斷。但對于每個結(jié)點的調(diào)整而言，其實是向下調(diào)整。
（一）調(diào)整成大頂堆
第一步
?找到最后一個非葉子結(jié)點為“數(shù)組長度/2-1=5/2-1=1【索引i=1】”，也就是上圖中的結(jié)點36。，開始進(jìn)行判斷該子樹是否滿足堆的性質(zhì)。
?可以發(fā)現(xiàn)以該結(jié)點為根結(jié)點的子樹不滿足大頂堆的結(jié)構(gòu)，找到子結(jié)點元素最大的那一個【兩個子結(jié)點為arr[i* 2+1]與arr[i* 2+2]，也就是arr[3]與arr[4]】，進(jìn)行調(diào)整，如下圖所示：
第二步
?繼續(xù)找到上一個非葉子結(jié)點，也就是結(jié)點18【索引i=0】，按照相同方法進(jìn)行調(diào)整。
?結(jié)點調(diào)換之后，需要繼續(xù)判斷換下后的結(jié)點是否符合堆的特性【也就是以當(dāng)前結(jié)點18為根的子樹】。發(fā)現(xiàn)不符合，繼續(xù)調(diào)整。此時結(jié)點18的索引i=1，從其左右孩子結(jié)點中選擇最大的一個進(jìn)行調(diào)換，結(jié)果如下：
第三步
?發(fā)現(xiàn)沒有非葉子結(jié)點了，這時調(diào)整結(jié)束。此時得到的就是最大堆。
?仔細(xì)分析，發(fā)現(xiàn)可以通過一個外層的循環(huán)從最后一個非葉子結(jié)點開始進(jìn)行遍歷【所有非葉子結(jié)點】，注意這里非葉子結(jié)點的訪問順序是自底向上。循環(huán)體用來判斷是否滿足堆的性質(zhì)來決定是否進(jìn)行調(diào)整。每次進(jìn)行調(diào)整時需要判斷交換后的結(jié)點是否也滿足堆的性質(zhì)，不滿足要繼續(xù)進(jìn)行同樣的調(diào)整，這里是一個向下調(diào)整的過程?？梢园l(fā)現(xiàn)這其實是一個遞歸的過程【當(dāng)然也可以采用迭代的方式實現(xiàn)】。因此代碼設(shè)計上可以采用“循環(huán)+遞歸”或者“循環(huán)+迭代”的方法。
示例代碼如下：
#include<iostream>
using namespace std;
/**
* 遞歸實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
void AdjustDown(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
// 左子節(jié)點索引超出計算范圍，直接返回。
if (li > len)
{
return;
}
// 先判斷左右子節(jié)點，哪個較大。
if (ri <= len && arr[li]<arr[ri])
{
cMax = ri;
}
//如果根結(jié)點小于葉子結(jié)點，交換
if (arr[index]<arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax, len); // 如果父節(jié)點被子節(jié)點調(diào)換，則需要繼續(xù)判斷換下后的父節(jié)點是否符合堆的特性。
}
}
/**
* 迭代實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
void maxHeapAdjust(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int item=arr[index]; //存儲該索引結(jié)點
while(li<len)
{
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
// 先判斷左右子節(jié)點，哪個較大。
if (ri<=len && arr[li]<arr[ri])
{
cMax=ri;
}
//如果根結(jié)點小于葉子結(jié)點，交換
if (item>=arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子節(jié)點值賦值給父結(jié)點
li=cMax*2+1;//找到以cMax值為索引的結(jié)點的左孩子結(jié)點
ri=li+1;
}
arr[li/2]=item; //找到正確位置賦值
}
int main()
{
int len=15;
int arr[len]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int maxIndex = len - 1; //最大索引
int beginIndex = len/ 2 - 1; //最后一個非葉子結(jié)點索引
/*
* 將數(shù)組堆化
* beginIndex = 第一個非葉子節(jié)點。
* 從第一個非葉子節(jié)點開始即可。無需從最后一個葉子節(jié)點開始。
* 葉子節(jié)點可以看作已符合堆要求的節(jié)點，根節(jié)點就是它自己且自己以下值為最大。
* 循環(huán)遍歷
*/
for (int i = beginIndex; i >= 0; i--)
{
//maxHeapAdjust(arr, i, maxIndex);
AdjustDown(arr, i, maxIndex);
}
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
（二）調(diào)整成小頂堆
?我們來把上述得到的最大堆來調(diào)整成最小堆。也就是下圖：
第一步
?找到最后一個非葉子結(jié)點為“數(shù)組長度/2-1=5/2-1=1【索引i=1】”，也就是上圖中的結(jié)點40。，開始進(jìn)行判斷該子樹是否滿足堆的性質(zhì)。
?可以發(fā)現(xiàn)以該結(jié)點為根結(jié)點的子樹不滿足最小堆的結(jié)構(gòu)，找到子結(jié)點元素最小的那一個【兩個子結(jié)點為arr[i* 2+1]與arr[i* 2+2]，也就是arr[3]與arr[4]】，進(jìn)行調(diào)整，如下圖所示：
第二步
?繼續(xù)找到上一個非葉子結(jié)點，也就是結(jié)點47【索引i=0】，按照相同方法進(jìn)行調(diào)整。
第三步
?發(fā)現(xiàn)沒有非葉子結(jié)點了，這時調(diào)整結(jié)束。此時得到的就是最大堆。
?代碼設(shè)計邏輯基本上是一樣的。
示例代碼
#include<iostream>
using namespace std;
/**
* 遞歸實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
void AdjustDown(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
// 左子節(jié)點索引超出計算范圍，直接返回。
if (li > len)
{
return;
}
// 先判斷左右子節(jié)點，哪個較小。
if (ri <= len && arr[ri]<arr[li])
{
cMax = ri;
}
//如果根結(jié)點大于葉子結(jié)點，交換
if (arr[index]>arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax, len); // 如果父節(jié)點被子節(jié)點調(diào)換，則需要繼續(xù)判斷換下后的父節(jié)點是否符合堆的特性。
}
}
/**
* 迭代實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
void maxHeapAdjust(int *arr, int index, int len)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int item=arr[index]; //存儲該索引結(jié)點
while(li<len)
{
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
// 先判斷左右子節(jié)點，哪個較小。
if (ri<=len && arr[ri]<arr[li])
{
cMax=ri;
}
//如果根結(jié)點小于葉子結(jié)點，交換
if (item<arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子節(jié)點值賦值給父結(jié)點
li=cMax*2+1;//找到以cMax值為索引的結(jié)點的左孩子結(jié)點
ri=li+1;
}
arr[li/2]=item; //找到正確位置賦值
}
int main()
{
int len=5;
int arr[len]={47,40,45,18,36};
int maxIndex = len - 1; //最大索引
int beginIndex = len/ 2 - 1; //最后一個非葉子結(jié)點索引
/*
* 將數(shù)組堆化
* beginIndex = 第一個非葉子節(jié)點。
* 從第一個非葉子節(jié)點開始即可。無需從最后一個葉子節(jié)點開始。
* 葉子節(jié)點可以看作已符合堆要求的節(jié)點，根節(jié)點就是它自己且自己以下值為最小。
* 循環(huán)遍歷
*/
for (int i = beginIndex; i >= 0; i--)
{
//maxHeapAdjust(arr, i, maxIndex);
AdjustDown(arr, i, maxIndex);
}
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
(三)時間復(fù)雜度分析
?假設(shè)二叉樹的高度為k，則從倒數(shù)第二層右邊的節(jié)點開始，這一層的節(jié)點都要執(zhí)行子節(jié)點比較然后交換（如果順序是對的就不用交換）；倒數(shù)第三層呢，則會選擇其子節(jié)點進(jìn)行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。如果交換了，那么又要選擇一支子樹進(jìn)行比較和交換；高層也是這樣逐漸遞歸。
?小編來分析下這個時間復(fù)雜度求解的過程。
?1、n為結(jié)點的個數(shù)，樹的高度（即堆的高度）為h【樹的高度與深度相等】
?2、由于是自底向上，從右至左調(diào)整構(gòu)建堆，因此在調(diào)整上層元素的時候，并不需要同下層所有元素進(jìn)行比較，只需要同其中一個分支進(jìn)行比較，而做比較的次數(shù)則是樹的高度減去當(dāng)前結(jié)點的高度。第i層上結(jié)點元素的個數(shù)為2(i-1)，(h-i)表示每個結(jié)點要比較的次數(shù)。因此，第i層所有結(jié)點的總比較次數(shù)為T(i)=2(i-1) * (h-i)。
?3、因此，總的計算時間：
?S=T(h-1)+T(h-2)+……+T(1)=2(h-2)* 1+2(h-3)* 2+……+(h-1)
?注意：因為葉子層不用交換，所以i從h-1開始到1，第一個非葉子結(jié)點所在層所有結(jié)點的高度都為1。
?可以發(fā)現(xiàn)該數(shù)列為等差數(shù)列和等比數(shù)列的乘積，利用錯位相減法可進(jìn)行解決。
?2S=2(T(h-1)+T(h-2)+……T(1))=2(h-1)* 1+2(h-2)* 2+……+2* (h-1)
?2S-S=2(h-1)+2(h-2)+2(h-3)+……+2-(h-1)
?除最后一項外，這就是個等比數(shù)列，直接用上求和公式：
?Sn=a1* (1-qn)/(1-q)(q≠1)
?得到：S=2h-h-1
?因為h為完全二叉樹的高度，因此有：2(h-1)<n<2h，總之可以認(rèn)為：h=logn （實際計算得到應(yīng)該是 log2n+1 < h <= log2n ）;
?綜上所述得到：S = n - logn -1
?所以時間復(fù)雜度為：O(n)（堆的初始化過程）。
三、堆元素的插入
?剛已經(jīng)分析了堆的初始化過程，那接下來我們來探究下，怎樣往一個堆里面去插入數(shù)據(jù)。
（一）基本插入過程
?堆的插入操作是自底向上進(jìn)行的【這里指每個結(jié)點是向上進(jìn)行調(diào)整】，每次從堆的最后一個結(jié)點開始插入（將插入的值放入完全二叉樹的最后一個結(jié)點），為了維持堆的性質(zhì)，還要從插入結(jié)點開始依次往前遞歸，去維持堆的三個特性。
?取插入結(jié)點的父節(jié)點，比較父節(jié)點的值和插入結(jié)點的值，將較小的值交換到父節(jié)點位置。再以父節(jié)點為當(dāng)前結(jié)點，重復(fù)上一步操作，直到遇到父節(jié)點比插入結(jié)點值小，就可以結(jié)束遞歸。
（二）實例分析
?這里僅以大頂堆作為例子講解，用的還是上述得到的大頂堆，我們來往堆里插入新的元素。
?我們現(xiàn)在有這樣的三個數(shù)46、70、50等待我們插入，一起來分析下。
插入46：
?得到下圖：
?
插入70
?得到下圖：
?發(fā)現(xiàn)交換后的結(jié)點70已經(jīng)是根節(jié)點，那么本次插入到此結(jié)束。
插入50：
?得到下圖：
?取插入結(jié)點50的父節(jié)點18，比較父節(jié)點的值和插入結(jié)點的值，發(fā)現(xiàn)不滿足最大堆的性質(zhì)，將較大的值交換到父節(jié)點位置。重復(fù)相同的操作，最終得到下圖：
（三）代碼示例
?根據(jù)上述分析，可得到代碼如下：
//迭代
bool Heap<T>::insert(const T& val)
{
/*
最大堆特點是根結(jié)點比子節(jié)點都大
根據(jù)該性質(zhì)進(jìn)行調(diào)整
(1)索引為i的左孩子的索引是 (2i+1)
（2）索引為i的右孩子的索引是 (2i+2)
（3）索引為i的父結(jié)點的索引是 (i-1)/2
*/
int i=len++;
while(i>0 && heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
i=(i-1)/2;
}
heap[i]=val;
return true;
}
//遞歸
template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
int i=len++;
AdjustUps(val,i);
}
template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
if(i<0)
{
return;
}
if(heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
heap[(i-1)/2]=val;
i=(i-1)/2;
AdjustUps(val,i);
}
}
（四）時間復(fù)雜度分析
?我們可以看到，每個結(jié)點的插入都和樹的深度有關(guān)，并且都是不斷的把樹折半來實現(xiàn)插入，因此是典型的遞歸【當(dāng)然用迭代法也可實現(xiàn)，道理一樣】。
?插入一個新的結(jié)點后樹的結(jié)點數(shù)為n，高度為h，那么此時結(jié)點要交換的最多次數(shù)為：S=h-1
?因為h為完全二叉樹的高度，因此有：2(h-1)<n<2h，總之可以認(rèn)為：h=logn （實際計算得到應(yīng)該是 log2n+1< h < log2n ）;
?所以S=O(logn)-1
?插入的時間復(fù)雜度為O(logn)。
四、堆元素的查找
?堆元素的查找相對還是比較簡單，對于一顆滿二叉樹來說，n個節(jié)點的二叉排序樹的高度為log2(n+1),其查找效率為O(log2n)，也就是O(logn)，近似于折半查找。
?同樣，查找可以有迭代和遞歸兩種實現(xiàn)方法，代碼如下所示：
//非遞歸實現(xiàn)
template<typename T>
int Heap<T>::search(const T& val)
{
int i=0;
while(i<len)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
i++;
}
}
//遞歸實現(xiàn)
template<typename T>
int Heap<T>::find(const T& val)
{
_find(val,0);
}
template<typename T>
int Heap<T>::_find(const T& val,int i)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
_find(val,i++);
}
五、堆元素的刪除
?接下來我們來關(guān)注下堆里元素的刪除。我們還是以下圖作為例子來看看怎么進(jìn)行刪除【大頂堆】。
?首先找到結(jié)點50對應(yīng)位置的索引,把當(dāng)前堆的最后一個結(jié)點的值賦到當(dāng)前位置，然后刪除最后一個結(jié)點，堆的當(dāng)前長度減1。得到下圖：
?那么接下來就是對當(dāng)前結(jié)點18進(jìn)行調(diào)整。調(diào)整的方式與上述一致。這里只放個圖片：
?因此對于堆里元素的刪除，基本過程就是：
?（1）找到待刪除元素的位置索引
?（2）將堆的最后一個元素賦值到該位置上，堆的容量減1
?（3）進(jìn)行堆結(jié)構(gòu)的調(diào)整
?代碼如下所示：
template<typename T>
bool Heap<T>::deletes(const T& val)
{
int i=search(val);
heap[i]=heap[len-1];
len--;
AdjustDown(heap,i);
//maxHeapAdjust(heap,i);
}
六、堆排序
（一）基本思想
?1、將待排序序列構(gòu)造成一個大頂堆【小頂堆】，此時，整個序列的最大值【最小值】就是堆頂?shù)母?jié)點。
?2、將其與末尾元素進(jìn)行交換，此時末尾就為最大值【最小值】。
?3、然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值【次大值】。如此反復(fù)執(zhí)行，便能得到一個有序序列了。
?注意：降序排序使用大頂堆，升序排序使用小頂堆。
（二）基本步驟
1、構(gòu)造初始堆
?小編前面已經(jīng)分析了大頂堆與小頂堆的各種有關(guān)操作。所以這里構(gòu)造初始堆的步驟不再做解釋。堆創(chuàng)建成功之后，接下來就是堆的調(diào)整使最后的數(shù)組有序。
2、調(diào)整堆
?這里小編僅以大頂堆作為例子。將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。小編用上述得到的大頂堆來進(jìn)行演示，也就是下圖：
?1、將堆頂元素47和末尾元素36進(jìn)行交換
?重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義，得到下圖：
?2、再將堆頂元素45與末尾元素18進(jìn)行交換，得到下圖：
?重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義，得到下圖：
（三）時間復(fù)雜度分析
?調(diào)整堆的復(fù)雜度計算和初始化堆差不多，都為O(logn)。又因為堆排序每個結(jié)點都要進(jìn)行一次調(diào)整，因此堆排序的總時間復(fù)雜度為O(nlogn)。
（四）示例代碼
?小編自己寫了大頂堆的相關(guān)操作代碼，包括創(chuàng)建，堆化、查找、刪除、排序等等。小頂堆這里不做分享，原理一樣的。代碼如下所示：
#include <stdio.h>
#include <iostream>
using namespace std;
/*
本程序中堆的起始索引為0
*/
// 堆的實現(xiàn),二叉樹用數(shù)組來表示
template<typename T>
class Heap
{
public:
Heap(const int& size); //創(chuàng)建堆
~Heap();
bool insert(const T& val); //堆插入非遞歸
bool deletes(const T& val);//堆刪除非遞歸
void AdjustUp(const T& val);//堆插入調(diào)整
void AdjustUps(const T& val,int i);//向上調(diào)整
void Delete(const T& val); //刪除堆中某個數(shù)
int search(const T& val); //迭代查找堆中某個數(shù)所在位置
int find(const T& val); //遞歸查找堆中某個數(shù)所在位置
int _find(const T& val,int i); //遞歸查找堆中某個數(shù)所在位置
void AdjustDown(T* arr, int index) ;//遞歸調(diào)整最大堆 ---向下調(diào)整
void maxHeapAdjust(T* arr, int index) ;//迭代調(diào)整最大堆
void ArrToHeap(T* arr); //數(shù)組轉(zhuǎn)換為堆
void AdjustToHeap(T* arr,int arrlength) ;//將數(shù)組元素拷貝到堆中再進(jìn)行調(diào)整，調(diào)整后的heap支持插入刪除等操作
void HeapSort(); //大頂堆排序，升序，最大值放最后位置
void ArrToHeapToSort(T* arr); //傳入數(shù)組轉(zhuǎn)換成堆進(jìn)行排序
void print(); //打印堆元素
private:
T* heap; //堆
int MaxSize,len,temp; //MaxSize為堆最大容量，Nel為堆目前元素個數(shù),
};
template<typename T>
Heap<T>::Heap(const int& size)
{
MaxSize = 2*size;
heap =new T[MaxSize];
len=size;
}
template<typename T>
Heap<T>::~Heap()
{
delete []heap;
heap = NULL;
MaxSize = 0;
}
/**
* 遞歸實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
template<typename T>
void Heap<T>::AdjustDown(T* arr, int index)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
int maxIndex = len - 1; //最大索引
// 左子節(jié)點索引超出計算范圍，直接返回。
if (li > maxIndex)
{
return;
}
// 先判斷左右子節(jié)點，哪個較大。
if (ri <= maxIndex && arr[li]<arr[ri])
{
cMax = ri;
}
//如果根結(jié)點小于葉子結(jié)點，交換
if (arr[index]<arr[cMax])
{
int item=arr[index];
arr[index]=arr[cMax];
arr[cMax]=item;
AdjustDown(arr, cMax); // 如果父節(jié)點被子節(jié)點調(diào)換，則需要繼續(xù)判斷換下后的父節(jié)點是否符合堆的特性。
}
}
/**
* 迭代實現(xiàn)
* 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
* @param arr 列表
* @param index 需要堆化處理的數(shù)據(jù)的索引
* @param len 未排序的堆（數(shù)組）的長度
*/
template<typename T>
void Heap<T>::maxHeapAdjust(T* arr, int index)
{
int li = (index * 2) + 1; // 左子節(jié)點索引
int ri = li + 1; // 右子節(jié)點索引
int item=arr[index]; //存儲該索引結(jié)點
int maxIndex = len - 1; //最大索引
while(li<maxIndex)
{
int cMax = li; // 子節(jié)點值最大索引，默認(rèn)左子節(jié)點。
// 先判斷左右子節(jié)點，哪個較大。
if (ri<=maxIndex && arr[li]<arr[ri])
{
cMax=ri;
}
//如果根結(jié)點小于葉子結(jié)點，交換
if (item>=arr[cMax])
{
break;
}
arr[li/2]=arr[cMax];//把子節(jié)點值賦值給父結(jié)點
li=cMax*2+1;//找到以cMax值為索引的結(jié)點的左孩子結(jié)點
ri=li+1;
}
arr[li/2]=item; //找到正確位置賦值
}
/*
將數(shù)組調(diào)整為堆
*/
template<typename T>
void Heap<T>::ArrToHeap(T* arr)
{
int beginIndex = len/ 2 - 1; //最后一個非葉子結(jié)點索引
/*
* 將數(shù)組堆化
* beginIndex = 第一個非葉子節(jié)點。
* 從第一個非葉子節(jié)點開始即可。無需從最后一個葉子節(jié)點開始。
* 葉子節(jié)點可以看作已符合堆要求的節(jié)點，根節(jié)點就是它自己且自己以下值為最大。
* 循環(huán)遍歷
*/
for (int i = beginIndex; i >= 0; i--)
{
maxHeapAdjust(arr, i);
// AdjustDown(arr, i);
}
}
/*
將數(shù)組元素拷貝到heap數(shù)組中再進(jìn)行調(diào)整
調(diào)整后的heap支持插入刪除等操作
*/
template<typename T>
void Heap<T>:: AdjustToHeap(T* arr,int arrlength)
{
for(int i=0;i<arrlength;i++)
{
heap[i]=arr[i];
}
int beginIndex = len/ 2 - 1; //最后一個非葉子結(jié)點索引
/*
* 將數(shù)組堆化
* beginIndex = 第一個非葉子節(jié)點。
* 從第一個非葉子節(jié)點開始即可。無需從最后一個葉子節(jié)點開始。
* 葉子節(jié)點可以看作已符合堆要求的節(jié)點，根節(jié)點就是它自己且自己以下值為最大。
* 循環(huán)遍歷
*/
for (int i = beginIndex; i >= 0; i--)
{
maxHeapAdjust(heap, i);
// AdjustDown(arr, i);
}
}
template<typename T>
bool Heap<T>::insert(const T& val)
{
/*
最大堆特點是根結(jié)點比子節(jié)點都大
根據(jù)該性質(zhì)進(jìn)行調(diào)整
(1)索引為i的左孩子的索引是 (2i+1)
（2）索引為i的右孩子的索引是 (2i+2)
（3）索引為i的父結(jié)點的索引是 (i-1)/2
*/
int i=len++;
while(i>0 && heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
i=(i-1)/2;
}
heap[i]=val;
return true;
}
template<typename T>
void Heap<T>::AdjustUp(const T& val)
{
int i=len++;
AdjustUps(val,i);
}
template<typename T>
void Heap<T>::AdjustUps(const T& val,int i)
{
if(i<0)
{
return;
}
if(heap[(i-1)/2]<val)
{
heap[i]=heap[(i-1)/2];
heap[(i-1)/2]=val;
i=(i-1)/2;
AdjustUps(val,i);
}
}
//非遞歸實現(xiàn)
template<typename T>
int Heap<T>::search(const T& val)
{
int i=0;
while(i<len)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
i++;
}
}
//遞歸實現(xiàn)
template<typename T>
int Heap<T>::find(const T& val)
{
_find(val,0);
}
template<typename T>
int Heap<T>::_find(const T& val,int i)
{
if(heap[i]==val)
{
return i;
}
if(heap[2*i+1]==val)
{
return 2*i+1;
}
if(heap[2*i+2]==val)
{
return 2*i+2;
}
_find(val,i++);
}
template<typename T>
bool Heap<T>::deletes(const T& val)
{
int i=search(val);
heap[i]=heap[len-1];
len--;
AdjustDown(heap,i);
//maxHeapAdjust(heap,i);
}
template<typename T>
void Heap<T>::HeapSort()
{
int index=len-1;
int tmplen=len;
while(index>=0)
{
int tmp=heap[index];
heap[index]=heap[0];
heap[0]=tmp;
len--;
index--;
AdjustDown(heap,0);
}
len=tmplen;
}
template<typename T>
void Heap<T>::ArrToHeapToSort(T* arr)
{
ArrToHeap(arr);
int index=len-1;
int tmplen=len;
while(index>=0)
{
int tmp=arr[index];
arr[index]=arr[0];
arr[0]=tmp;
len--;
index--;
AdjustDown(arr,0);
}
len=tmplen;//恢復(fù)堆長度
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
}
template<typename T>
void Heap<T>::print()
{
for(int i=0;i<len;i++)
{
cout<<heap[i]<<" ";
}
}
int main()
{
int arr[5]={18,36,45,40,47};
int arrlength=sizeof(arr)/sizeof(arr[0]);
Heap<int> max_heap(arrlength);
//max_heap.ArrToHeapToSort(arr);
max_heap.AdjustToHeap(arr,arrlength);
//max_heap.HeapSort();
max_heap.AdjustUp(46);
max_heap.AdjustUp(70);
max_heap.AdjustUp(50);
//cout<<max_heap.search(50)<<endl;
cout<<max_heap.find(50)<<endl;
//max_heap.insert(46);
//max_heap.deletes(50);
max_heap.print();
return 0;
}
七、堆應(yīng)用之“優(yōu)先級隊列”
（一）隊列與優(yōu)先隊列的區(qū)別
?1、隊列是一種FIFO（First-In-First-Out）先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，對應(yīng)于生活中的排隊的場景，排在前面的人總是先通過，依次進(jìn)行。
?2、優(yōu)先隊列是特殊的隊列，從“優(yōu)先”一詞，可看出有“插隊現(xiàn)象”。比如在火車站排隊進(jìn)站時，就會有些比較急的人來插隊，他們就在前面先通過驗票。優(yōu)先隊列至少含有兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert（插入），即將元素插入到優(yōu)先隊列中（入隊）；以及deleteMin（刪除最小者），它的作用是找出、刪除優(yōu)先隊列中的最小的元素（出隊）。
?3、優(yōu)先隊列的實現(xiàn)常選用二叉堆，在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊列一般也是指堆。
（二）C++優(yōu)先隊列簡介
?優(yōu)先隊列在頭文件#include <queue>中；其聲明格式為：priority_queue <int> q;【聲明一個名為q的整形的優(yōu)先隊列】。
?支持的操作:
?q.empty() //如果隊列為空，則返回true，否則返回false
?q.size() //返回隊列中元素的個數(shù)
?q.pop() //刪除隊首元素，但不返回其值
?q.top() //返回具有最高優(yōu)先級的元素值，但不刪除該元素
?q.push(item) //在基于優(yōu)先級的適當(dāng)位置插入新元素
?有關(guān)操作不做介紹了。
八、一點總結(jié)
?堆的使用場景還是非常豐富的，掌握堆的各種操作很有必要。啰里啰唆寫了一大堆，或多或少存在些錯誤，也請指正，謝謝！
