首先看完全二叉樹的定義：
若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。
如果一個完全二叉樹的某個結點值都不大于或小于他的父結點，那就叫做堆。根結點是所有結點裡最大的叫大根堆，最小的叫小根堆。
比如：
9-1 a是大根堆，9-2 a是小根堆，剩下的都不是堆（因為不是完全二叉樹）。
那麼怎麼樣才能構造出堆呢？
把一棵樹結點按順序标号
從後往前找到第一個有孩子的結點（肯定在倒數第二排，最後一排已經是堆），看以這個結點為根結點的樹滿不滿足堆的條件，如果不滿足就和下面的交換，直到滿足堆的條件。就這麼一個一個結點檢查，一直到根結點，堆就完成了~
比如到結點4（大根堆），15比17小，17沒孩子，是以隻要把15和17換就行了，此時結點4是17，結點8是15，再到結點2的時候，因為12比17小，是以把17移動到結點2，12又比15小，是以把15移動到結點4，最後把12移動到結點8。
為什麼要從後往前呢？這是因為在檢查一個結點的時候，如果以他孩子為根結點的樹已經是堆，就隻要找到這個點應該插入的位置，把子結點都往上移一個就行了~
小根堆代碼：
void heapadjust(int i,int l) //檢查結點函數，i是這個結點的位置，l是堆的結點數，設根結點為0
{
int child,t;
for(t=a[i]; i*2+1<l; i=child) //i*2+1是左孩子，t是檢查的結點的值
{
child=i*2+1; // i是父結點
if(child+1<l&&a[child+1]<a[child]) child++; //如果右孩子比左孩子小（取最小的孩子）
if(t>a[child]) a[i]=a[child]; //如果最小的孩子比t小，就把那個孩子的值給父結點
else break;
}
a[i]=t; //此時已經找到該放的位置，插入t
}
void heapsort(int l)
{
int i,temp;
for(i=l/2-1; i>=0; i--) heapadjust(i,l); //從第1個有孩子的結點開始找，一直到根結點
}
大根堆隻要把符号改一下就行了，方法是一樣的~
void maxheap_add(int x){
Lmax++;
int child=Lmax,fa=child>>1;
while(fa>0&&a[fa]<x){
a[child]=a[fa];
child=fa;
fa>>=1;
}
a[child]=x;
}
void minheap_add(int x){
Lmin++;
int child=Lmin,fa=child>>1;
while(fa>0&&b[fa]>x){
b[child]=b[fa];
child=fa;
fa>>=1;
}
b[child]=x;
}
void maxheap_adjust(int x){
int t=a[x],fa=x,child=fa<<1;
while(child<=Lmax){
if(child+1<=Lmax&&a[child+1]>a[child]) child++;
if(t<a[child]){
a[fa]=a[child];
fa=child;
child=fa<<1;
}
else break;
}
a[fa]=t;
}
void minheap_adjust(int x){
int t=b[x],fa=x,child=fa<<1;
while(child<=Lmin){
if(child+1<=Lmin&&b[child+1]<b[child]) child++;
if(t>b[child]){
b[fa]=b[child];
fa=child;
child=fa<<1;
}
else break;
}
b[fa]=t;
}
int maxheap_del(){
int t=a[1];
a[1]=a[Lmax];
Lmax--;
maxheap_adjust(1);
return t;
}
int minheap_del(){
int t=b[1];
b[1]=b[Lmin];
Lmin--;
minheap_adjust(1);
return t;
}
堆隻能保證根結點最大或最小，其他元素并不一定是有序的，但隻要每次把根結點和最後一個結點交換，再把剩下無序的結點調整成堆，再把根結點放到後面，再。。重複。。直到最後一個結點，就排完序了~
void heapsort(int l)
{
int i,temp;
for(i=l/2-1; i>=0; i--) heapadjust(i,l);
for(i=l-1;i>0;i--){
temp=a[0]; //交換最後一個和根結點
a[0]=a[i];
a[i]=temp;
heapadjust(0,i);} // 這時除根結點，其他本來已經都是堆，隻需檢查根結點
}
下面來說優先隊列（也是剛發現這個東東。。原理就是堆吧），具體的我也說不好，就簡單說下怎麼用吧
首先頭檔案裡要有#include<queue>，
最小值優先：priority_queue<int,vector<int>,greater<int> >q;
最大值優先：priority_queue<int,vector<int>,less<int> >q;
第一個int就是int類型的，vector<int>就是預設的什麼=。=我也搞不懂，寫上就行了。。
，greater是最小值優先，less是最大值優先。
順便說一下STL隊列（不是優先隊列）
queue <int> q;
Push()：入隊，即插入元素
Pop()：出隊，即删除元素
Front()：讀取隊首元素
Back()：讀取隊尾元素
Empty()：判斷隊列是否為空
Size()：隊列目前元素
杭電4006
The kth great number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 4790 Accepted Submission(s): 1962
Problem Description Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.
Input There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an " I" followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a "Q", then you need to output the kth great number.
Output The output consists of one integer representing the largest number of islands that all lie on one line.
Sample Input
8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q
Sample Output
1
2
3
Hint
Xiao Ming won't ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=<k<=n<=1000000).
剛開始做的是插入元素後就堆排序，輸出時就輸出a[k]，怎麼都逾時。。後來發現。。隻要隻在數組裡儲存k個，在開始構造成一個最小堆，再插入時隻要比較要插入的元素和堆的根結點哪個大，如果它比根結點大，就用它代替根結點，這時因為底下的都已經是堆，是以隻要調用那個檢查結點函數檢查根結點就行~（并不需要每次都排序，隻要保證堆中k個元素都是目前最大的k個，輸出時直接輸出根結點就行了（k個最大的裡面的最小的））。這道題用優先隊列更簡單~
最小堆：
#include<stdio.h>
int a[1000010];
void heapadjust(int i,int l)
{
int child,t;
for(t=a[i]; i*2+1<l; i=child)
{
child=i*2+1;
if(child+1<l&&a[child+1]<a[child]) child++;
if(t>a[child]) a[i]=a[child];
else break;
}
a[i]=t;
}
void heapsort(int l)
{
int i,temp;
for(i=l/2-1; i>=0; i--) heapadjust(i,l);
}
int main()
{
freopen("D:\\CodeBlocks\\file\\in.txt","r",stdin);
int n,k,t;
char s[5];
while(scanf("%d%d",&n,&k)!=EOF)
{
int l=k,i;
for(i=0; i<k; i++)
scanf("%s%d",s,&a[i]);
heapsort(k);
n-=k;
while(n--)
{
scanf("%s",s);
if(s[0]=='I')
{
scanf("%d",&t);
if(t>a[0])
{
a[0]=t;
heapadjust(0,k);
}
}
else
{
printf("%d\n",a[0]);
}
}
}
return 0;
}
優先隊列：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int main()
{
freopen("D:\\CodeBlocks\\file\\in.txt","r",stdin);
int n,k,t;
char s[5];
while(scanf("%d%d",&n,&k)!=EOF)
{
priority_queue<int,vector<int>,greater<int> >q;
int i,t;
for(i=0; i<n; i++)
{
scanf("%s",s);
if(s[0]=='I')
{
scanf("%d",&t);
if(q.size()<k) q.push(t);
else
{
q.push(t);
q.pop();
}
}
else printf("%d\n",q.top());
}
}
return 0;
}