叠甲：
> 本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。
堆及堆的性质
> 堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
>
> 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 priority_queue 其实就是一个大根堆。
>
> （小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
-- OI wiki
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
堆使用数组进行储存。对于第 iii 个节点，其父节点下标为 i2\frac{i}{2}2i ，左右孩子节点下标分别为 2×i2 \times i2×i 与 2×i+12\times i+12×i+1 。
（小根）堆元素的插入与取出
1. 在堆尾加入该元素，并把这个节点设为当前节点。
2. 比较当前节点与父节点的大小：
2.1 如果当前节点小于父节点，交换他们的值，并把父节点设为当前节点，重复步骤 2。
2.2 若当前节点大于父节点，或该节点已经为根节点，停止。
小根堆插入代码实现：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 取出堆的根结点的值
2. 把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。
3. 把根结点置为当前父结点 。
4. 如果当前父节点无儿子（parent>len/2parent >len/2parent>len/2），则结束；否则，把当前父节点的两（或一）个儿子中值最小的那个设置为当前的子结点。
5. 比较当前父节点与当前子节点的值，如果当前父节点的值小于或等于当前子节点的值，则结束；否则，交换这两个结点的值，把当前父节点指向当前子节点，继续执行步骤 4。
小根堆取出当前节点并删除当前节点代码实现（这里分为 top 和 pop ）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
手写堆模版：
小根堆：
大根堆：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
真题演练：
题目
题目大意：
给你 NNN 个数，要求输出他们从小到大排列的结果。
思路：
这里我们使用堆排序。
很简单，首先构建一个堆，将这 NNN 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。
代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
超市
题目大意：
超市里有 NNN 件商品，每件商品都有利润 pip_ipi 和过期时间 did_idi ，每天只能卖一件商品，过期商品不能再卖。
求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
其中 N≤2×105N\leq 2\times 10^5N≤2×105。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本题有两种做法，一种是采用贪心的策略，但是可能会爆。所以我们用堆。
先预处理所有商品，构建一个结构体并按照过期时间进行排序。
建立一个小根堆（这里采用 STL 容器的方式）。由于一天只能卖一个商品，所以堆的大小就是卖商品的天数。如果当前的商品过期天数与当前卖商品的天数相等，我们就看堆顶的那件商品（因为是小根堆，所以这件商品的收益肯定最小）的收益，如果比这件商品小，我们就替换掉。否则直接添加至堆中即可（因为已经排过序了）。
CODE
