堆结构和lambda表达式的应用（IPO问题）

之前有篇文章讲解了堆结构以及堆排序，堆可以分为大根堆和小根堆，那么我们如何使用么？笔试时需不需要自己重新实现一个堆结构呢？这个问题怎么说，从底层实现是应该会的，也不难，但实际用的时候就不用自己重新造轮子了！C++标准库中有类似堆结构的东西——Priority_Queue!

lambda表达式()

段落部分内容来源转自简书--小白将

在开始今天的内容之前，我们先来说一说C++中的lambda表达式，大家学过Python的都知道lambda表达式的好处，可以省略大量代码而且使得阅读逻辑更加清晰，在C++中其表现结构一般为：

[ 俘获变量 ] （形参） { 函数体 }

lambda表达式最前面的方括号的意义何在？其实这是lambda表达式一个很要的功能，就是闭包。lambda表达式的大致原理：每当你定义一个lambda表达式后，编译器会自动生成一个匿名类（这个类当然重载了()运算符），我们称为闭包类型（closure type）。那么在运行时，这个lambda表达式就会返回一个匿名的闭包实例，其实一个右值。所以，我们上面的lambda表达式的结果就是一个个闭包。闭包的一个强大之处是其可以通过传值或者引用的方式捕捉其封装作用域内的变量，前面的方括号就是用来定义捕捉模式以及变量，我们又将其称为lambda捕捉块。 捕获的方式可以是引用也可以是复制，但是具体说来会有以下几种情况来捕获其所在作用域中的变量：

那么捕获域是怎么使用呢？我们可以看下面的例子：

int main(int argc, char** argv){
    int x =10;
    auto add_x = [x](int a){return a+x;};
    auto multipy_x = [&x](int a){return a*x;};

    cout<<"add "<<add_x(10)<<" "<<"multipy "<< multipy_x(10)<<endl;
}

其中必须要记住的几种形式：

• []：默认不捕获任何变量；
• [=]：默认以值捕获所有变量；
• [&]：默认以引用捕获所有变量；
• [x]：仅以值捕获x，其它变量不捕获；
• [&x]：仅以引用捕获x，其它变量不捕获；
• [=, &x]：默认以值捕获所有变量，但是x是例外，通过引用捕获；
• [&, x]：默认以引用捕获所有变量，但是x是例外，通过值捕获；
• [this]：通过引用捕获当前对象（其实是复制指针）；
• [*this]：通过传值方式捕获当前对象；

一般我们通常使用前三种形式！！！

PriorityQueue(优先级队列)

C++标准库中的优先级队列其底层数据一般为vector形式，并以堆结构进行数据管理的，我们通过前面的知识也知道堆分为大根堆和小根堆，其中大根堆的根节点是最大值，而小根堆的根节点是最小值。因此，我们在定义PriorityQueue时候需要指定其比较器，特别是当存储类型为自定义对象时！

我们首先来看PriorityQueue的模板定义，其中less< value_type >是一个标准库中的函数对象，因此我们知道了 模板参数中的第三个位置是一个比较函数的函数对象。因此我们可以自己新建一个函数对象来进行传递！

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

下面例子介绍了几种构造优先级队列的方法：

• 通过一个类重载()来构成函数对象，用于自定义比较器使用
• 对于基础类型，可以使用标准库中的函数对象，如less和more
• 使用lambda表达式，由于lambda表达式返回的是一个匿名对象，因此必须在实例化同时将其作为参数传递到priority_queue中去！
• 构建的比较器中<表示less（降序）表示小根堆，反之>表示大根堆

#include <queue>
#include <vector>
#include <iostream>

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

class myGreater{
public:
    bool operator()(const int a, const int b){
        return a > b;
    }
};

int main() {
// 情况1： 默认为大根堆，相当于<int, vector<int>, less<int>> q;
    std::priority_queue<int> q;  
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
    print_queue(q);
// 情况2：自定义函数对象
    std::priority_queue<int, std::vector<int>, myGreater > q2; 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
    print_queue(q2);
// 情况3：使用lambda表达式构建，decltype获取匿名函数类型
    auto cmp = [](int left, int right) { return left < right;};  
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
    print_queue(q3);
}

IPO问题

（来自LeetCode）为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。 给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。 例子： 输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1]. 输出: 4 解释: 由于你的初始资本为 0，你尽可以从 0 号项目开始。在完成后，你将获得 1 的利润，你的总资本将变为 1。此时你可以选择开始 1 号或 2 号项目。由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。因此，输出最后最大化的资本，为 0 + 1 +3 = 4。

算法原理： 这个问题使用最大堆和最小堆就可以很简单的实现，并且我们使用贪心算法，具体的贪心策略如下：

1. 首先将每个项目按照所需要的资本排序放进最小堆中，然后逐个取出堆顶的元素并进行判断是否小于初始资金W，这样就可以得到当前可以启动的项目的集合！
2. 然后 将这个项目集合按照获得的收益放进最大堆，然后取出这个堆顶也就是最大的收益，相加后得到新的资金W，然后再去判断最小堆中是否可以解锁新的项目，如果有，添加到最大堆，如果没有，继续执行取出最大堆堆顶的操作！
3. 这样保证了我们做的每个项目都是收益最高，而且是满足条件（资金允许）可以做的！ 具体代码为：

// 第二种形式，使用pair方式，只能传递二个参数
int findMaximizedCapital(int k, int W, vector<int> &Profits, vector<int> &Capital)
{
    // pair<int, int> cost, profit
    auto cmp1 = [](const pair<int, int> &a, const pair<int, int> &b) {
        if(a.first > b.first){
            return true;
        }   // 小根堆
        return false;
    };

    auto cmp2 = [](const pair<int, int> &a, const pair<int, int> &b) {
        if(a.second < b.second){
            return true;
        }   // 大根堆
        return false;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp1)> minCost(cmp1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp2)> maxProfit(cmp2);
    for (int i = 0;i < Profits.size(); i++){
        minCost.emplace(Capital[i], Profits[i]);
    }
    for (int i = 0;i < k; i++){
        while(!minCost.empty() && minCost.top().first <= W){
            maxProfit.push(minCost.top());
            minCost.pop();
        }
        if(maxProfit.empty()){
            cout << endl;
            return W;
        }
        W += maxProfit.top().second;
        cout << maxProfit.top().second << "...";
        maxProfit.pop();
    }
    cout << endl;
    return W;
}

我们可以看到，上述题目用到了pair类型，但这里的参数只有资金和利润，如果更多的话可以使用一个类的形式，这个完整版程序可以关注公众号获取哦！

资源分享

以上完整代码文件（C++版）,文件名为：IPO问题，请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~

公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)