## 1.堆

（二叉）堆是数组，可看成近似的完全二叉树。例如A[1..n]中，A[i]的父节点是A[i/2],左右孩子分别为A[2i],A[2i+1]（假设都存在）。

```Parent(i)
return i / 2```
```Left(i)
return 2 * i```
```Right(i)
return 2 * i + 1```

A[Parent(i)] >= A[i]

A[Parent(i)] <= A[i]

## 2.维护堆的性质

```Max-Heapify(A, i) // 修改判断大小即可变为维护最小堆性质
l = Left(i)  // 左孩子下标
r = Right(i) // 右孩子下标
if l <= A.heap-size and A[l] > A[i]
largest = l
else
largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
Max-Heapify(A, largest) // 防止交换后largest节点不满足```

## 3.构建堆

```Build-Max-Heap(A)
A.heap-size = A.length
for i=A.length/2 downto 2
Max-Heapify(A, i)```

## 4.堆排序

```Heapsort(A)
Build-Max-Heap(A) // 构建最大堆
for i=A.length downto 2
exchange A[i] with A[1]
A.heap-size = A.heap-size - 1
Max-Heapify(A, 1)```

（PS：用栈可实现从大到小排序）

## 5.优先队列

```Heap-Maximum(A)
return A[1]```

```Heap-Extract-Max(A)
if A.heapsize < 1
error"heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
Max-Heapify(A, 1)
return max```

```Heap-Increase-Key(A, i, key)
if A[i] > key
error
A[i] = key
while i > 1 and A[i] > A[Parent(i)]
exchange A[i] with A[Parent(i)]
i = Parent(i)```

```Max-Heap-Insert(A, key)
A.heap-size = A.heap-size + 1
A.[A.heap-size] = -∞
Heap-Inscrease-Key(A, A.heap-size, key)```

# 警告！！！以下为C++代码！！！！

```#include<iostream>
using namespace std;
int a[100005] = {0}, n, size;
int parent(int i) //叫爸爸
{
return i / 2;
}
int left(int i) //左儿子
{
return i * 2;
}
int right(int i) //右儿子
{
return i * 2 + 1;
}
void Max_Heapify(int a[], int i) //让爸爸最大
{
int l = left(i);
int r = right(i);
int largest = 0;
if(l <= size && a[l] > a[i])
largest = l;
else
largest = i;
if(r <= size && a[r] > a[largest])
largest = r;
if(largest != i)
{
swap(a[i], a[largest]);
Max_Heapify(a, largest);
}
}
void Build_Max_Heap(int a[]) //使数组成为最大堆
{
for(int i = n / 2; i >= 1; i--)
Max_Heapify(a, i);
}
void Heapsort(int a[]) //堆排序，最大堆的根节点为堆的最大值
{
Build_Max_Heap(a);
for(int i = n; i >= 2; i--)
{
swap(a[1], a[i]);
size--;
Max_Heapify(a, 1);
}
}
int main()
{
cin>>n;
size = n;
for(int i = 1; i <= n; i++)
cin>>a[i];
Heapsort(a);
for(int i = 1; i <= n; i++)
cout<<a[i]<<" ";
return 0;
}```
```优先队列：
#include<iostream>
#include<cmath>
using namespace std;
int a[100005] = {0}, n, size;
int parent(int i) //叫爸爸
{
return i / 2;
}
int left(int i) //左儿子
{
return i * 2;
}
int right(int i) //右儿子
{
return i * 2 + 1;
}
void Max_Heapify(int a[], int i) //让爸爸最大
{
int l = left(i);
int r = right(i);
int largest = 0;
if(l <= size && a[l] > a[i])
largest = l;
else
largest = i;
if(r <= size && a[r] > a[largest])
largest = r;
if(largest != i)
{
swap(a[i], a[largest]);
Max_Heapify(a, largest);
}
}
void Build_Max_Heap(int a[]) //使数组成为最大堆
{
for(int i = n / 2; i >= 1; i--)
Max_Heapify(a, i);
}
void Heapsort(int a[]) //堆排序，最大堆的根节点为堆的最大值
{
Build_Max_Heap(a);
for(int i = n; i >= 2; i--)
{
swap(a[1], a[i]);
size--;
Max_Heapify(a, 1);
}
}
int Heap_Maximum(int a[]) //返回堆最大值
{
return a[1];
}
int Heap_Extract_Max(int a[]) //返回堆最大值并删除
{
int max = a[1];
a[1] = a[size];
size--;
Max_Heapify(a, 1);
return max;
}
void Heap_Increase_Key(int a[], int i, int key) //让a[i]增加到key
{
if(a[i] > key)
cout<<"error"<<endl;
else
{
a[i] = key;
while(i > 1 && a[i] > a[parent(i)])
{
swap(a[i], a[parent(i)]);
i = parent(i);
}
}
}
int main()
{
cout<<"输入数组大小：";
cin>>n;
size = n;
cout<<"输入数组元素：";
for(int i = 1; i <= n; i++)
cin>>a[i];
Build_Max_Heap(a);
for(int j = 1, i = 1; i <= n; i++)
{
cout<<a[i]<<" ";
if(i == pow(2, j)-1)
{
cout<<endl;
j++;
}
}
cout<<endl<<"输入改变元素及值:";
int x, y;
cin>>x>>y;
size = n;
Heap_Increase_Key(a, x, y);
for(int j = 1, i = 1; i <= n; i++)
{
cout<<a[i]<<" ";
if(i == pow(2, j)-1)
{
cout<<endl;
j++;
}
}
cout<<endl<<"Max:"<<Heap_Maximum(a)<<endl;
int maxi = Heap_Extract_Max(a);
cout<<"Max:"<<maxi<<", Size:"<<size;
return 0;
}```