堆，又可以稱為優先級隊列，這種數據結構插入和刪除操作需要o(lgn)的時間復雜度，但是卻能在o(1)的時間復雜度內取出最大值或最小值。
堆有最大堆和最小堆，最大堆中任意節點的關鍵碼大於或等於它的左、右子女的關鍵碼，相反，最小堆中任意節點的關鍵碼小於或等於它的左、右子女的關鍵碼。
如果堆的索引從0開始，則有如下關系式：
(1)左子女：2*i+1
(2)右子女：2*i+2
(3)父親節點：向下取整((i-1)/2)
注：這是索引，給定一個數組長度，應該先通過len-1得到最後一個元素的索引，在通過第三條的公式開始調整。
堆的調整
（1）向下調整（刪除堆頂元素）
/*copyright@ CNV && lsj*/
/*最小堆*/
#include<iostream>
#include<algorithm>
using namespace std;
#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)<<1)+2)
#define CHILD(i) (((i)-1)>>1)
typedef int RecType;
/*從上往下調整 ---刪除堆頂元素的調整*/
void SiftDown(RecType minHeap[],int low,int high)
{
int i = low;
int j = LEFT(i);
int base = minHeap[i];
while(j<=high){
//與小的比較,必須是j<high沒有等號
if(j<high && minHeap[j+1]<minHeap[j])j++;
if(base<=minHeap[j])break;
else{
//上移
minHeap[i] = minHeap[j];
i = j;
j = LEFT(i);
}
}
minHeap[i] = base;
};
/*copyright@ CNV && lsj*/
/*最小堆*/
#include<iostream>
#include<algorithm>
using namespace std;
#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)<<1)+2)
#define CHILD(i) (((i)-1)>>1)
typedef int RecType;
/*從上往下調整 ---刪除堆頂元素的調整*/
void SiftDown(RecType minHeap[],int low,int high)
{
int i = low;
int j = LEFT(i);
int base = minHeap[i];
while(j<=high){
//與小的比較,必須是j<high沒有等號
if(j<high && minHeap[j+1]<minHeap[j])j++;
if(base<=minHeap[j])break;
else{
//上移
minHeap[i] = minHeap[j];
i = j;
j = LEFT(i);
}
}
minHeap[i] = base;
};
（2）向上調整（插入元素，插入堆尾部）
[cpp
/*從下往上調整 ---往堆中插入元素的調整*/
void SiftUp(RecType minHeap[],int high)
{
int j = high;
int i = CHILD(j);
int base = minHeap[j];
while(i>0){
if(minHeap[i]<=base)break;
else{
//下移
minHeap[j] = minHeap[i];
j = i;
i = CHILD(j);
}
}
minHeap[j] = base;
};
/*從下往上調整 ---往堆中插入元素的調整*/
void SiftUp(RecType minHeap[],int high)
{
int j = high;
int i = CHILD(j);
int base = minHeap[j];
while(i>0){
if(minHeap[i]<=base)break;
else{
//下移
minHeap[j] = minHeap[i];
j = i;
i = CHILD(j);
}
}
minHeap[j] = base;
};
（3）堆排序
[cpp]
//逆序--》從大到小
void HeapSort(RecType arr[],int len)
{
int lastIndex = len -1;//由長度轉換為索引
int beginIndex = (lastIndex-1)>>1;
//下面構建了一個堆,o(nlogn)
while(beginIndex>=0){
SiftDown(arr,beginIndex,len-1);
--beginIndex;
}
//排序
for(int i=len-1;i>=0;i--){
swap(arr[0],arr[i]);
SiftDown(arr,0,i-1);
}
};
//逆序--》從大到小
void HeapSort(RecType arr[],int len)
{
int lastIndex = len -1;//由長度轉換為索引
int beginIndex = (lastIndex-1)>>1;
//下面構建了一個堆,o(nlogn)
while(beginIndex>=0){
SiftDown(arr,beginIndex,len-1);
--beginIndex;
}
//排序
for(int i=len-1;i>=0;i--){
swap(arr[0],arr[i]);
SiftDown(arr,0,i-1);
}
};
STL中的堆（面試的時候用得著）
（1）利用make_heap構建堆（STL源碼剖析P181）
STL提供堆結構，但卻是幕後工作者，heap可以分為max_heap和min_heap。記住幾個重要的接口：make_heap、push_heap、pop_heap、sort_heap。
這幾個接口輸入參數是這樣的：
template<class RandomAccessIterator,Class Compare>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);
注：通過給上面各函數傳入不同的仿函數，分別構造最大堆還是最小堆
[cpp]
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
vector<int>ivec(arr,arr+9);
//greater<int> comp;//最小堆
less<int> comp;//最大堆
make_heap(ivec.begin(),ivec.end(),greater<int>,comp);
//9 5 8 3 4 0 2 3 1
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
cout<<endl;
ivec.push_back(7);
push_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
cout<<endl;
pop_heap(ivec.begin(),ivec.end(),comp);
cout<<ivec.back()<<endl;//9
ivec.pop_back();
sort_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
system("pause");
return 0;
}
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
vector<int>ivec(arr,arr+9);
//greater<int> comp;//最小堆
less<int> comp;//最大堆
make_heap(ivec.begin(),ivec.end(),greater<int>,comp);
//9 5 8 3 4 0 2 3 1
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
cout<<endl;
ivec.push_back(7);
push_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
cout<<endl;
pop_heap(ivec.begin(),ivec.end(),comp);
cout<<ivec.back()<<endl;//9
ivec.pop_back();
sort_heap(ivec.begin(),ivec.end(),comp);
//9 7 8 3 5 0 2 3 1 4
for(int i=0;i<ivec.size();++i){
cout<<ivec[i]<<" ";
}
system("pause");
return 0;
}
（2）利用priority_queue構建堆（STL源碼剖析P183，其實利用了上面的接口）
STL中提供了一種priority_queue，缺省情況下利用max_heap完成。STL中的priority_queue往往不被歸類為容器，而是被歸類為容器迭代器。
STL中的聲明priority_queue聲明如下：
template<class T,class Sequence = vector<T>,class Compare=less<typename Sequence::value_type>>
class priority_queue{
....
}
從上面的定義看出，STL的priority_queue采用vector實現，且Compare比較函數為仿函數less，我們可以傳入greater，構造最小堆。
[cpp]
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue<int> ipq(arr,arr+9);
cout<<"size="<<ipq.size()<<endl;
while(!ipq.empty()){
cout<<ipq.top()<<" ";
ipq.pop();
}
system("pause");
}<SPAN style="FONT-SIZE: 18px">
</SPAN>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue<int> ipq(arr,arr+9);
cout<<"size="<<ipq.size()<<endl;
while(!ipq.empty()){
cout<<ipq.top()<<" ";
ipq.pop();
}
system("pause");
}
換一個仿函數就能構造最小堆：
[cpp]
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue<int，vector<int>,greater<int>> ipq(arr,arr+9);
cout<<"size="<<ipq.size()<<endl;
while(!ipq.empty()){
cout<<ipq.top()<<" ";
ipq.pop();
}
system("pause");
return 0;
}
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,5,8,9,3,5};
priority_queue<int，vector<int>,greater<int>> ipq(arr,arr+9);
cout<<"size="<<ipq.size()<<endl;
while(!ipq.empty()){
cout<<ipq.top()<<" ";
ipq.pop();
}
system("pause");
return 0;
}
（3）利用set（或者multiset）構建堆（劍指offer P169頁）
[cpp]
#include<iostream>
#include<algorithm>
#include<functional>
#include<set>
using namespace std;
typedef greater<int> Greater;//最大堆
typedef less<int> Less;//最小堆
typedef multiset<int,Less> MaxHeap;
typedef multiset<int,Less>::iterator Iterator;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
MaxHeap heap;
for(int i=0;i<9;i++){
heap.insert(arr[i]);
}
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
cout<<endl;
heap.erase(heap.begin());
heap.insert(10);
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
system("pause");
return 0;
}
#include<iostream>
#include<algorithm>
#include<functional>
#include<set>
using namespace std;
typedef greater<int> Greater;//最大堆
typedef less<int> Less;//最小堆
typedef multiset<int,Less> MaxHeap;
typedef multiset<int,Less>::iterator Iterator;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
MaxHeap heap;
for(int i=0;i<9;i++){
heap.insert(arr[i]);
}
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
cout<<endl;
heap.erase(heap.begin());
heap.insert(10);
for(Iterator it = heap.begin();it!=heap.end();++it){
cout<<*it<<" ";
}
system("pause");
return 0;
}[cpp]
<P></P><PRE></PRE>
<PRE></PRE>
<PRE></PRE>
