二叉堆

堆

先讲一下堆是啥：是数据结构的一种，他们具有树状结构，就分为根节点和子节点，也就是一个父亲后面跟着两个孩子，跟他父亲有一定的关系~~父子没关系就很抽象~~
堆也分为大根堆和小根堆，大根堆顾名思意，根节点的数据大于子节点，可以理解成父亲比儿子们老；小根堆也就是根节点的数据小于子节点。

二叉堆（Binary Heap）是最简单、常用的堆，是一棵符合堆的性质的完全二叉树，具体可以看二叉堆这篇文章,里面有可视化的二叉堆，方便理解，二叉堆是用于实现优先队列的数据结构之一，手写二叉堆可以加深对它的理解，也能实现相较于优先队列快一些的功能

对于一个二叉堆，我们要去调整他们的关系，呈现出大根堆或小根堆的结构，就得理解它是怎么上浮或下沉的

Size 是 堆的长度，然后heap就是堆的数组

上浮

也就是把底层元素按照我们所需要的关系去向上调整（这里以小根堆为例，大根堆就把大于号换成小于号就行啦）

void up(int x){
    while(x / 2 >= 1 && heap[x / 2] > heap[x]){//小根堆的根节点要小于父节点
        swap(heap[x / 2],heap[x]);//交换
        x >>= 1;//把位置向上调整
    }
}

下沉

就是上浮的反义词嘛偷个懒

void down(int x){
    while(x * 2 <= Size && heap[x * 2] < heap[x]){
        swap(heap[x * 2],heap[x]);
        x <<= 1;
    }
}

现在仔细思考一下，发现下沉函数有点怪怪的，怎么就只有一个节点，另一个不比较吗其实我忘打了o(TヘTo),所以就再改进一下

int son_max(int x){
    return  2 * x + (2 * n + 1 <= Size && heap[2 * x + 1] < heap[x]);
}
void down(int x){
    while(son_max(x) <= Size && heap[son_max(x)] < heap[x]){
        swap(heap[son_max(x)],heap[x]);
        x = son_max(x);
    }
}

现在二叉堆的排序问题已经解决，建议自己画个图去实操一下，更好理解；接下来，我们平时使用优先队列，会发现有push和pop、top这些函数，那我们是否也可以实现，

当然是可以实现的，接下来讲解这三个函数该怎么去设计

插入

就是将元素插入进堆里面，但是插进去我们要维护一下堆的原本秩序，所以就需要去调整它的位置，所以就要用up

void insert(int x){
    heap[++ Size] = x;//放在最后一个位置
    up(Size);
}

删除

删除头顶的数据，最开始我就让它等于0，但是堆的秩序就乱了，而且不方便我们进行排序，那该怎么办才能让它不影响堆的秩序，让它在最后一个不就可以，那么就得需要跟最后一个数交换，再对交换的数字进行维护

void pop(){
    swap(heap[1],heap[Size]);
    heap[Size --] = 0;
    down(1);
}

头顶

这个简单，就返回头顶元素就行

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

到这里就基本上结束了，整体的模板在下面呈现

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

const int maxn = 1e6 + 10;
int n,op,Size;
int heap[maxn];//堆

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

int son_max(int x){
	return 2 * x + (2 * x + 1 <= Size && heap[2 * x + 1] < heap[2 * x]);
}//寻找最大的子节点

void down(int x){
	while(son_max(x) <= Size && heap[son_max(x)] < heap[x]){
		int to = son_max(x);
		swap(heap[to],heap[x]);
		x = to;
	}
}

void insert(){
	int x;
	cin >> x;
	heap[++ Size] = x;
	up(Size);
}//插入

void pop(){
	swap(heap[Size],heap[1]);
	heap[Size] = 0;
	Size --;
	down(1);
}//删除

void top(){
	cout << heap[1] << endl;
}//头部输出

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	while(cin >> n){
            memset(heap,0,sizeof(heap));
 
	    这里进行数据输入即可
            进行对堆的建立
	}
	return 0;
}

这里还有用结构体封装的堆，代码如下

struct Heap
{
	int heap[maxn],Size;

	void clear(){
		memset(heap,0,sizeof(heap));
		Size = 0;
	}//初始化

	void up(int x){
		while(x / 2 >= 1 && heap[x / 2] > heap[x]){
			swap(heap[x / 2],heap[x]);
			x >>= 1;
		}
	}//向上浮动

	int son_max(int x){
		return 2 * x + (2 * x + 1 <= Size && heap[2 * x + 1] < heap[2 * x]);
	}//寻找最大的子节点

	void down(int x){
		while(son_max(x) <= Size && heap[son_max(x)] < heap[x]){
			int to = son_max(x);
			swap(heap[to],heap[x]);
			x = to;
		}
	}//向下调整

	void insert(int x){
		heap[++ Size] = x;
		up(Size);
	}//插入

	void pop(){
		swap(heap[Size],heap[1]);
		heap[Size--] = 0;
		down(1);
	}//删除

	int top(){
		return heap[1];
	}//头顶值
}h;//小根堆结构体封装

写着写着，突然发现有一部分题目不太像普通的二叉堆，后面上网冲冲浪，发现是可反悔堆，结合了贪心的思想，下面部分题目也是可反悔堆，所以没时间了TAT下次再update，做的题目全乱了o(TヘTo)

下面就是部分题单还有部分没解决，解决了速速update

1、P3378 【模板】堆

2、P1334 瑞瑞的木板

3、POJ2442 --- Sequence

4、POJ1456 --- Supermarket

5、P2949 [USACO09OPEN]Work Scheduling G

6、P4053 [JSOI2007] 建筑抢修

7、AcWing147 --- 数据备份

注：题解还没准备好o(TヘTo)，日后速速解决