分享4道关于堆的题目，欢迎批评指正~
题目1：数据流中的第K大元素（leetcode-703）
题目描述
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
- int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
样例输入
["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
样例输出
[null, 4, 5, 5, 8, 8]
题目分析
统计一组数据的第K大元素，我们只需要记录前K大元素，不需要记录所有数据。而第K大元素，在前K大元素中，是最小的。因此可以通过小顶堆实现本题目。
依次遍历每一个数据，若输入数据数量小于K，则直接入堆；若数据数量大于等于K，如果当前数据大于堆顶元素，则弹出堆顶元素，并将当前元素入堆。
遍历完成后，返回堆顶元素。
最终代码
class KthLargest { public: typedef pairs; KthLargest(int k, vector & nums) { this->k = k; for(auto x : nums){ add(x);//通过调用add实现数据的添加 } return ; } int add(int val) { if(s.size() < k) { s.insert(PII(val, tot++)); } else{ if(s.begin()->first < val){ s.erase(s.begin()); s.insert(PII(val, tot++)); } } return s.begin()->first; } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */
题目2：数据流的中位数（leetcode-295）
题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如 arr = [2,3,4] 的中位数是 3 。
- 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
-
MedianFinder() 初始化 MedianFinder 对象。
-
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
-
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
样例输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]
样例输出
[null, null, null, 1.5, null, 2.0]
题目分析
我们只关注数据中间的一个或两个数字，因此可以将数据从中间分成两段，左段比中位数小，右段比中位数大，前者为大顶堆，后者为小顶堆。我们通过维护，保证要么两个堆的数据数量相等，要么左段的堆的数据量多一个。具体流程如下：
- 当插入一个新的元素，首先根据元素的大小选择插入左右哪个堆：如果新的数据大于左堆的堆顶元素，则将数据插入右堆，否则插入左堆；
- 插入元素后，根据左右堆的元素数量，对两个堆进行维护；
- 最后根据左右两个堆的数量，计算中位数。
最终代码
class MedianFinder { public: typedef pairs1, s2; MedianFinder() { tot = 0; } void addNum(int num) { if(s1.size() == 0 || num < -s1.begin()->first){ s1.insert(PII(-num, tot++)); } else{ s2.insert(PII(num, tot++)); } int n1 = (s1.size() + s2.size() + 1) / 2;//根据两堆的元素数量进行维护 if(s1.size() == n1) return ; if(s1.size() < n1) { s1.insert(PII(-s2.begin()->first, tot++)); s2.erase(s2.begin()); } else { s2.insert(PII(-s1.begin()->first, tot++)); s1.erase(s1.begin()); } return ; } double findMedian() { int t = s1.size() + s2.size(); if(t % 2){ return -s1.begin()->first; } double a = -s1.begin()->first; double b = s2.begin()->first; return (a + b) / 2.0; } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
题目3：丑树（leetcode-264）
题目描述
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
样例输入
10
样例输出
12
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
题目分析
本题的关键在于如何生成一个丑数序列，若某个数是丑数，则这个数的两倍、三倍、五倍也都是丑数。可以用小顶堆来存储丑数，每次弹出堆顶的元素，同时让堆顶元素的两倍、三倍、五倍入堆，迭代n次。
为提高运算效率，可以对代码进行改进。按照上面的解法有可能产生重复的数，例如弹出2后，会将4、6、10入堆，下面在弹出3时，会让6、9、15入堆，次数6被入堆了两次。虽然set可以筛掉重复的数，但是重复操作会降低效率。
因此，为了避免重复，在弹出某个数字后，首先求该数字的最大因子，当最大因子是2，则将这个数的2倍、3倍、5倍入堆；当最大因子是3，则将这个数的3倍和5倍入堆；当最大质因子是5，则将这个数的5倍入堆。这样就避免了冲入数字的入堆操作。（虽然会增加额外的判断和计算，但实测整体效率更高）
最终代码
class Solution { public: int nthUglyNumber(int n) { sets; s.insert(1); long long ans = 0; int flag = 0; while(n--) { ans = *s.begin(); s.erase(s.begin()); if(ans % 5 == 0) flag = 2;//根据堆顶元素的最大因子，判断入堆的情况 else if(ans % 3 == 0) flag = 1; else flag = 0; switch (flag){ case 0: s.insert(ans * 2); case 1: s.insert(ans * 3); case 2: s.insert(ans * 5); break; } } return ans; } };
题目4：超市买货
题目描述
超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.
样例输入
每组数据第一行为一个整数N(0
之后N行，每行各有两个整数, 第i行为pi,di(1<=pi,di<=10000)
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
样例输出
输出当前条件下超市的最大利润.
185
题目分析
题目比较复杂，不知道该怎样下手，遇到这种情况可以对样例数据进行操作，从中找突破口。
我们从第零天开始分析，首先肯定出售保质期短的商品，因为保质期长的商品可以未来出售。“20，1”和“2，1”两个商品的保质期都是一天，但前者利润更高，因此第一天售卖“20，1”。接下来是“100，2”和“8，2”，前者利润更高，因此 第二天售卖“100，2”。
因此，可以按照保质期从短到长遍历每个商品，每卖出一个商品，天数加一。当遍历到第x个商品，如果该商品没有过保质期，则当天就买此商品；如果商品的保质期已过，为获得最大利润，可以对之前的售卖策略进行调整，如果当前商品的利润大于现有方案中利润最小商品的利润，则用当前商品替换利润最小的商品。
最终代码
#include
#include using namespace std; int main(){ int N, ans = 0; typedef pair D;//记录每个商品的保质期 set ARR;//记录已售卖的商品 cin >> N; int p[N], d[N]; for(int i = 0; i < N; i++){ cin >> p[i] >> d[i]; D.insert(PII(d[i], i)); } int num, di, pi; int day = 0; while(!D.empty()){ num = D.begin()->second; di = D.begin()->first; pi = p[num]; D.erase(D.begin()); if(ARR.empty() || di > day) { ans += pi; day++; ARR.insert(PII(pi, num)); } else if(ARR.begin()->first < pi){ ans -= ARR.begin()->first; ans += pi; ARR.erase(ARR.begin()); ARR.insert(PII(pi, num)); } } cout << ans << endl; return 0; }
总结
利用堆结构，可以方便高效的取出数据中的最大或最小值。在处理复杂的极值问题时，可以通过实际操作、枚举结果等方式，分析出解决思路，对问题进行简化。例如题目1、2中，并不需要记录所有的数据，只需要记录极值等部分信息。
-