## 堆
本章主要介紹堆，下面是關于堆的一些主要操作：
~~~
// 最大堆實現, 數組下標從1開始，a[0]不使用。
// 交換兩數
void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}
// 把第i個元素向上移動
void ShiftUp(int a[], int i) {
while(i>1 && a[i]>a[i/2]) {
swap(a[i], a[i/2]);
i >>= 1;
}
}
// 把第i個元素向下移動
void ShiftDown(int a[], int n, int i) {
while((i=2*i) <= n) {
if(i+1<=n && a[i+1]>a[i]) ++i;
if(a[i] > a[i/2]) swap(a[i], a[i/2]);
else break;
}
}
// 把數組a變成具備最大堆性質的數組
void MakeHeap(int a[], int n) {
for(int i=n/2; i>0; --i)
ShiftDown(a, n, i);
}
// 向堆中插入元素x
void Insert(int a[], int &n, int x) {
a[++n] = x;
ShiftUp(a, n);
}
// 刪除堆中第i個元素
void Del(int a[], int &n, int i) {
a[i] = a[n--];
if(i>1 && a[i]>a[i/2]) ShiftUp(a, i);
else ShiftDown(a, n, i);
}
// 堆排序，時間復雜度O(nlogn)
void HeapSort(int a[], int n) {
MakeHeap(a, n);
for(int i=n; i>1; --i) {
swap(a[i], a[1]);
ShiftDown(a, i-1, 1);
}
}
~~~
