一、堆是什么？
堆是一棵完全二叉树
完全二叉树：除了最后一层节点，全部非空的二叉树，且最后一层节点从左往右排布
小根堆：每个节点都小于两个子节点
存储方式：一维数组，下标从1开始，下标x的左子节点是下标2x，右子节点是下标2x+1
二、如何手写一个堆？
- 初始化，读入堆
for (int i = 1; i <= n; i++) //n是堆的大小
scanf("%d", &h[i]);
::size = n;
for (int i = n / 2; i; i--) //循环到n也行，循环到n/2可以降低复杂度（证明略）
down(i);
- 插入一个数
//heap是存储堆的数组，size是堆的大小，x是待插入的数
heap[++size] = x; //先在堆底插入x
up(size); //将x上移至合适的位置
- 求集合当中的最小值
heap[1];
- 删除最小值
heap[1] = heap[size]; //先用最后一个点覆盖第一个点（最小值）
size--; //堆的大小-1
down(1); //将覆盖过来的值下沉
- 删除任意一个元素
//下标k为要删除的值的位置
heap[k] = heap[size]; //将堆底的值覆盖到k
size--; //堆的大小-1
down(k);
up(k); //覆盖过来的值要么应上移要么应下移要么不变，因为down和up函数都有执行条件，所以两个可以直接写上去，函数会判断执行哪个
- 修改任意一个元素
//下标k为要修改的值的位置
heap[k] = x;
down(k);
up(k);
后两个操作无法在STL堆中直接实现
- 如何上移和下移？
void down(int u) //下移
{
int t = u; //t表示左右子节点中最小值的编号
//下移过程中优先和最小的那个子节点交换
//下面的两个if同时保证了如果u已经满足了堆的性质，u不会下移
if (u * 2 <= size && h[u * 2] < h[t]) //如果u的左子节点存在且u的左子节点小于u
t = u * 2; //t设为左子节点
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) //如果u的右子节点存在且u的右子节点小于t
t = u * 2 + 1; //t设为右子节点
if (u != t) //如果找到了可以交换的数
{
swap(h[u], h[t]); //交换
down(t); //递归，直到u满足堆的性质为止
}
}
void up(int u) //上移
{
while (u / 2 && h[u / 2] > h[u]) //如果u的父节点不是根节点且父节点大于u
{
swap(h[u / 2], h[u]);
u /= 2;
}
}
三、总代码
#include <iostream>
const int N = 100010;
int n;
int h[N], size = 0;
using namespace std;
void down(int u) //下移
{
int t = u;
if (u * 2 <= ::size && h[u * 2] < h[t])
t = u * 2;
if (u * 2 + 1 <= ::size && h[u * 2 + 1] < h[t])
t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
void up(int u) //上移
{
while (u / 2 && h[u / 2] > h[u])
{
swap(h[u / 2], h[u]);
u /= 2;
}
}
void insert(int x) //插入x
{
h[++::size] = x;
up(::size);
}
int min() //求堆中的最小值
{
return h[1];
}
void delmin() //删除堆中最小值
{
h[1] = h[::size];
::size--;
down(1);
}
void del(int k) //删除下标k的元素
{
h[k] = h[::size];
::size--;
down(k);
up(k);
}
void write(int k, int x) //将下标为k的元素修改为x
{
h[k] = x;
down(k);
up(k);
}
int main()
{
//cin>>n;
//读入
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
::size = n;
for (int i = n / 2; i; i--)
down(i);
//....
}
四、配套练习