堆可被视为一颗完全二叉树。
堆在完全二叉树上加了性质：
1.大根堆：每个孩子节点小于等于其母亲节点
2.小根堆：每个孩子节点大于等于其母亲节点
对于左右孩子，其大小没有约束
有别于排序二叉树（左节点小于等于母亲节点小于等于右节点）
但不管是堆还是排序二叉树都是基于完全二叉树
存储可以使用结构体（struct)
存储完全二叉树：使用数组
编号为x的节点，在数组中下标为x的地方。
满足左儿子编号为母节点两倍，右儿子为左儿子加一
堆的操作：
1.加入元素
2.取出并删除元素
优先队列 是与堆有关的。
优先队列与队列 没有太大的关系。
补充:一些有关反悔贪心的题目可以使用优先队列来进行处理
相关题目:黑匣子
洛谷入口:链接
ACGO入口:链接
事先申明:接下来介绍的思路不是我自己想的,是抄洛谷题解的,摆在这里目的是为了我自己复习的时候方便看.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
此题需要优化 : n=2e5n=2e5n=2e5 时间限制是500ms500ms500ms
而优化的突破口则是"寻找第i小的数"
优化的思路则是创建两个优先队列,一个大根堆,一个小根堆.
(说实话觉得这个思路应该不难想,以前是做过建两个优先队列的题的,居然想了一个上午没想出来,以后要加强效率,想优化思路的时候要挖的再深一点)
设大根堆A,小根堆B
A.size()=iA.size()=iA.size()=i,其中存的是前i个最小值,而相应的A.top()A.top()A.top()就是要求的那个.
BBB存剩下的那些.
为防止出现A.top()<B.top()A.top()<B.top()A.top()<B.top()的情况,需要不断更新
