堆是一种支持插入、删除以及查找最值的数据结构，可以分为大根堆和小根堆。

1. 大根堆：树中的任意一个节点的权值都小于等于其父节点的权值（大根堆性质）。
2. 小根堆：树中的任意一个节点的权值都大于等于其父节点的权值（小根堆性质）。

二叉堆

二叉堆的本质是一颗具有堆性质的完全二叉树。

如何手写一个二叉堆（小根堆）？

堆的存储方式？

根据完全二叉树的性质，我们可以采用层次序列存储方式，直接使用数组来表示堆。数组的下标（从 1 开始）即是堆中节点的编号，而数组相应下标存储的值就是堆中节点的权值。

1. 节点 $i$ 的父节点：$\frac{i}{2}$（下取整）
2. 节点 $i$ 的左孩子：$2i$
3. 节点 $i$ 的右孩子：$2i+1$

完全二叉树的性质：

如果对一颗有$n$个结点的完全二叉树（其深度为$[log{2}^n]+1$）的结点按层序编号（从第一层到$[log{2}^n]+1$层，每层从左到右），对任一结点 i（$1\le i\le n$）:

1. 如果$i=1$，则结点 i 是二叉树的根，无双亲，如果 i>1,则其双亲结点是结点$[i/2]$
2. 如果$2i>n$，则结点 i 无左孩子（结点 i 为叶子结点）否则左孩子是结点$2i$。
3. 如果$2i+1>n$,则结点 i 无右孩子，否则其右孩子是结点$2i+1$.

堆支持的操作？

1. 向堆中插入一个数
2. 求堆中的最小值
3. 删除堆中的最小值
4. 删除堆中编号为 $k$ 的节点
5. 修改堆中编号为 $k$ 的节点

堆的两个核心函数

down(int k);

当堆中的k节点权值大于左右孩子的权值，使得整个堆不再满足小根堆性质时：down将节点k向下调整到合适的位置，使整个堆再度满足小跟堆性质。

up(int k);

当堆中的k节点权值小于父节点的权值，使得整个堆不再满足小根堆性质时：up将节点k向上调整到合适的位置，使整个堆再度满足小跟堆性质。

时间复杂度

需要明确的是无论是down操作还是up操作，它们的时间复杂度只和堆的高度有关，是 $O(\log n)$

作用

有了这两个核心函数，上面所说的堆支持的操作就可以借助它俩来实现：

1. 向堆中插入一个数：heap[++n] = x; up(n);
2. 求堆中的最小值：heap[1]
3. 删除堆中的最小值：heap[1] = heap[n]; n--; down(1)
4. 删除堆中编号为 $k$ 的节点：heap[k] = heap[n]; n--; down(k); up(k);
5. 修改堆中编号为 $k$ 的节点：heap[k] = x; down(k); up(k);

• 注：n为当前堆中节点个数
• 4，5 操作中的down(k)和up(k)只会执行一个，这样写是为了简化代码

建堆

向上调整

从空堆开始，一个一个的插入 $n$ 个元素，插入的同时进行向上调整，时间复杂度为 $O(n\log n)$

void build_heap(int n) {
	for (int i = 1; i <= n; i++) up(i);
}

向下调整

从节点编号约为 $\frac{n}{2}$ 开始到根节点结束，逐个向下调整。时间复杂度为 $O(n)$

上面的方法即是：每次「合并」两个已经调整好的堆，这说明了正确性。

void build_heap(int n) {
	for (int i = n / 2; i >= 1; i--) down(i);
}

示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int heap[N], n;

// 向下调整
void down(int u) {
	int t = u;
	if (u * 2 <= n && heap[u * 2] < heap[t]) t = u * 2;
	if (u * 2 + 1 <= n && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
	if (u != t) {
		swap(heap[u], heap[t]);
		down(t);
	}
}

// 向上调整
void up(int u) {
	while (u / 2 > 0 && heap[u / 2] > heap[u]) {
		swap(heap[u], heap[u / 2]);
		u /= 2;
	}
}

// 建堆
void build_heap(int n) {
	for (int i = n / 2; i >= 1; i--) down(i);
}

int main() {
	cin >> n; // 读入堆的大小
	for (int i = 1; i <= n; i++) cin >> heap[i];

	build_heap(n);

	return 0;
}

非递归版本的down

void down(int u) {
	while (u * 2 <= n) {
		int t = u * 2;
		if (t + 1 <= n && heap[t + 1] < heap[t]) t++;
		if (heap[t] >= heap[u]) break;
		swap(heap[u], heap[t]);
		u = t;
	}
}

代码实现

#include <bits/stdc++.h>
using namespace std;

int heap[1000];
int n, m;

void up(int u) {
	while (u / 2 > 0 && heap[u / 2] > heap[u]) {
		swap(heap[u/ 2], heap[u]);
		u /= 2;
	}
}

void down(int u) {
	int t = u; // 三者之间的最小值 编号
	if (2 * u <= n && heap[2 * u] < heap[t]) t = 2 * u;
	if (2 * u + 1 <= n && heap[2 * u + 1] < heap[t]) t = 2 * u + 1;
	if (t != u) {
		swap(heap[t], heap[u]);
		down(t);
	}
}

void insert(int x) {
	heap[++n] = x;
	up(n);
}

int get() {
	return heap[1];
}

void pop() {
	heap[1] = heap[n];
	n--;
	down(1);
}

void remove(int k) {
	heap[k] = heap[n];
	n--;
	down(k);
	up(k);
}

void modify(int k, int x) {
	heap[k] = x;
	down(k);
	up(k);
}

void build() {
	for (int i = n / 2; i >= 1; i--) down(i);
}

int main() {
	cin >> n; // 堆中初始有 n 个元素
	for (int i = 1; i <= n; i++) {
		cin >> heap[i];
	}

	build();

	cin >> m;
	while (m--) {
		int op, k, x;
		cin >> op;
		if (op == 1) {
			cin >> x;
			insert(x);
		} else if (op == 2) {
			cout << get() << endl;
		} else if (op == 3) {
			pop();
		} else if (op == 4) {
			cin >> k;
			remove(k);
		} else if (op == 5) {
			cin >> k >> x;
			modify(k, x);
		}
	}

    return 0;
}