数据结构笔记--优先队列（大小根堆）经典题型

1--项目的最大利润

题目描述：

        输入：正数数组 costs，costs[i] 表示项目 i 的花费；正数数组 profits，profits[i] 表示项目 i 的花费；正数 k 表示只能串行完成最多 k 个项目；m 表示拥有的资金，每完成一个项目后资金会立即更新（原始资金 + 利润）；

        输出：求解最后获得的最大利润；

主要思路：

        小根堆存储所有项目，大根堆存储可以进行的项目；

        每次从小根堆解锁项目添加到大根堆中，优先做大根堆利润最高的项目；

#include <iostream>
#include <vector>
#include <queue>struct project{project(int c, int p) : cost(c), profit(p) {}int cost;int profit;
};class cmp1{
public:bool operator()(project* a, project* b){return a->cost > b->cost;}
};struct cmp2{bool operator()(project* a, project* b){return a->profit < b->profit;}
};class Solution{
public:int findMaxCapital(int m, int k, std::vector<int> costs, std::vector<int> profits){std::priority_queue<project*, std::vector<project*>, cmp1> minCostQ;std::priority_queue<project*, std::vector<project*>, cmp2> maxProfitQ;// 按cost按从小到大排序项目for(int i = 0; i < profits.size(); i++){minCostQ.push(new project(costs[i], profits[i]));}for(int i = 0; i < k; i++){while(!minCostQ.empty() && minCostQ.top()->cost <= m){// 可以解锁新的项目maxProfitQ.push(minCostQ.top());minCostQ.pop();}if(maxProfitQ.empty()) return m; // 无法解锁新的项目，直接返回// 更新资金m += maxProfitQ.top()->profit;maxProfitQ.pop();}return m;}
};int main(int argc, char *argv[]){int m = 1;int k = 2;std::vector<int> costs = {1, 1, 2, 2, 3, 4};std::vector<int> profits = {1, 4, 3, 7, 2, 10};Solution S1;int res = S1.findMaxCapital(m, k, costs, profits);std::cout << res << std::endl; 
}

2--数据流的中位数

主要思路：

        分别使用大根堆和小根堆存储数据，每添加一个数据，先将数据添加至大根堆，再将数据弹出并添加到小根堆；

        当小根堆值的数量与大根堆值的数量相差 2 时，从小根堆弹出数据添加到大根堆中，保持两个根堆的容量差不超过；

        根据添加数据量是偶数还是奇数，返回对应的中位数；

#include <iostream>
#include <queue>class MedianFinder {
public:MedianFinder() {}void addNum(int num) {maxQ.push(num);minQ.push(maxQ.top());maxQ.pop();if(minQ.size() - maxQ.size() > 1){maxQ.push(minQ.top());minQ.pop();}}double findMedian() {// 奇数if((maxQ.size() + minQ.size()) % 2 != 0) return minQ.top();// 偶数else return( (maxQ.top() + minQ.top()) / 2.0);}
private:std::priority_queue<int, std::vector<int>, std::greater<int>> minQ;std::priority_queue<int, std::vector<int>, std::less<int>> maxQ;
};int main(int argc, char *argv[]){MedianFinder S1;S1.addNum(1);S1.addNum(2);S1.addNum(3);S1.addNum(4);S1.addNum(5);double res = S1.findMedian();std::cout << res << std::endl;
}