Derolol Blog

最小堆

排列组合 TopK 问题

优先队列 priority_queue

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int,vector<int>,less<int>> p1;     //默认大根堆
    p1.push(2); p1.push(1); p1.push(3);               //输出 3 2 1
    while(p1.empty()== false){
        cout<<p1.top()<<" ";
        p1.pop();
    }

    priority_queue<int,vector<int>,greater<int>> p2;  //小根堆
    p2.push(2); p2.push(1); p2.push(3);               //输出 1 2 3
    while(p2.empty()== false){
        cout<<p2.top()<<" ";
        p2.pop();
    }

    // 基本数据类型-pair-pair类型默认先比较第一个元素，第一个相等比较第二个
    priority_queue<pair<int, int> > a;
    a.push(pair<int,int>{1,2});
    a.push(pair<int,int>{1,3});
    a.push(pair<int,int>{2,5});
    while (a.empty()== false){
        cout<<a.top().first<<" "<< a.top().second<<endl;
        a.pop();
    }
    //输出:
    //2 5
    //1 3
    //1 2

    return 0;
}

多路归并

每次迭代有 N 个选择，将 N 个选择放入堆得到排序后的值

• 题型
  • 一维
    • 根据题意队列初始化 1 个值
  • 二维
    • 根据题意队列按序初始化 1 个列表
    • 初始化左上角值，set 判断是否重复插入
• 注意去重的问题

leetcode264 丑数 II（一维）

给你一个整数 n ，请你找出并返回第 n 个 丑数 。 丑数 就是质因子只包含 2、3 和 5 的正整数。

int nthUglyNumber(int n) {
    long times_num[] = {2, 3, 5};
    set<long> record;
    priority_queue<long, vector<long>, greater<long>> q;
    q.push(1);
    int index = 1;
    while (index <= n) {
        int cur_num = q.top();
        if (index == n) return cur_num;
        q.pop();
        for (long t : times_num) {
            long new_num = cur_num * t;
            if (record.contains(new_num)) continue;
            q.push(new_num);
            record.insert(new_num);
        }
        index ++;
    }
    return 0;
}

leetcode373 查找和最小的 K 对数字（二维）

给定两个以 非递减顺序排列 的整数数组 和 , 以及一个整数 。 定义一对值 ，其中第一个元素来自 ，第二个元素来自 。 请找到和最小的 k 个数对 。

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

    vector<vector<int>> result;
    int l1 = nums1.size(), l2 = nums2.size();

    auto cmp = [&](const auto& a, const auto& b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    for (int i = 0; i < l1; i ++) {
        q.push({i, 0});
    }

    while (result.size() < k) {
        auto [ia, ib] = q.top();
        result.push_back({nums1[ia], nums2[ib]});
        q.pop();
        if (ib + 1 < l2) q.push(pair<int, int>{ia, ib + 1});
    }

    return result;
}