# 堆
## 概念
堆（大頂堆，小頂堆）是一棵完全二叉樹，樹中每個節點的值都不小于（或不大于）其左右孩子節點的值。
### 數據結構
用數組存儲堆（完全二叉樹），節點可以按層序存儲于數組中。
```c++
// 堆數據結構
const int maxn=100;
// heap 為堆，n 為元素個數
int heap[maxn], n=10;
```
## 基本操作
### 向下調整
```C++
// heap 數組在 [low,high] 范圍內向下調整
void downAdjust(int low, int high){
int i=low,j=i*2；
while(j<=high){
if(j+1<=high &&heap[j+1]>heap[j])
j++;
if(heap[j]>heap[i]){
swap(heap[i],heap[j]);
i=j;
j=2*i;
}else break;
}
}
```
### 建堆
```c++
void createHeap(){
// 向下調整每個非葉子節點
for(int i=n/2;i>=1;i--){
downAdjust(i,n);
}
}
```
### 刪除對中最大元素
```c++
void deleteTop(){
heap[1]=heap[n--];
downAdjust(1,n);
}
```
### 向上調整
```c++
void upAdjust(int low, int high){
int i=high,j=i/2;
while(j>=low){
if(heap[i]>heap[j]){
swap(heap[i],heap[j]);
i=j;
j=i/2;
}else break;
}
}
```
### 插入元素
```c++
void insert(int x){
heap(++n)=x;
upAdjust(1,n);
}
```
## 堆排序
堆排序指使用堆結構對一個序列進行排序。
```c++
void heapSort(){
// 建完堆之后，二叉樹所有節點的值都不小于孩子節點
createHeap();
// 將序列排成按下標遞增的序列
for(int i=n;i>1;i--){
swap(heap[i],heap[1]);
downAdjust(1,i-1);
}
}
```
