heap_priority_queue.cpp

/*
Heap & Priority Queue Patterns
Mathematical Foundation: Complete binary tree, heap property
Max/Min heap operations: insert/extract O(log n), peek O(1)
Applications: Top K, merge K sorted, scheduling, Dijkstra
*/

#include <bits/stdc++.h>
using namespace std;

// Kth Largest Element in Array
// LeetCode: 215. Kth Largest Element in an Array
// https://leetcode.com/problems/kth-largest-element-in-an-array/
int findKthLargest(vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : a) {
        pq.push(x);
        if (pq.size() > k) pq.pop();
    }
    return pq.top();
}

// K Closest Points to Origin
// LeetCode: 973. K Closest Points to Origin
// https://leetcode.com/problems/k-closest-points-to-origin/
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    auto cmp = [](auto& a, auto& b) {
        return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
    for (auto& p : points) {
        pq.push(p);
        if (pq.size() > k) pq.pop();
    }
    vector<vector<int>> res;
    while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); }
    return res;
}

// Merge k Sorted Lists
// LeetCode: 23. Merge k Sorted Lists
// https://leetcode.com/problems/merge-k-sorted-lists/
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* head : lists) if (head) pq.push(head);
    
    ListNode dummy;
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}

// Find Median from Data Stream
// LeetCode: 295. Find Median from Data Stream
// https://leetcode.com/problems/find-median-from-data-stream/
class MedianFinder {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
public:
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        return maxHeap.size() > minHeap.size() ? maxHeap.top() : 
               (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

// Task Scheduler
// LeetCode: 621. Task Scheduler
// https://leetcode.com/problems/task-scheduler/
int leastInterval(vector<char>& tasks, int n) {
    vector<int> cnt(26);
    for (char c : tasks) cnt[c - 'A']++;
    sort(cnt.begin(), cnt.end());
    int mx = cnt[25] - 1;
    int idle = mx * n;
    for (int i = 24; i >= 0; i--) idle -= min(cnt[i], mx);
    return idle > 0 ? tasks.size() + idle : tasks.size();
}

// Top K Frequent Words
// LeetCode: 692. Top K Frequent Words
// https://leetcode.com/problems/top-k-frequent-words/
vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string,int> freq;
    for (string& w : words) freq[w]++;
    
    auto cmp = [](auto& a, auto& b) {
        return a.second == b.second ? a.first < b.first : a.second > b.second;
    };
    priority_queue<pair<string,int>, vector<pair<string,int>>, decltype(cmp)> pq(cmp);
    
    for (auto& p : freq) {
        pq.push(p);
        if (pq.size() > k) pq.pop();
    }
    
    vector<string> res;
    while (!pq.empty()) { res.push_back(pq.top().first); pq.pop(); }
    reverse(res.begin(), res.end());
    return res;
}

// Reorganize String
// LeetCode: 767. Reorganize String
// https://leetcode.com/problems/reorganize-string/
string reorganizeString(string s) {
    unordered_map<char,int> freq;
    for (char c : s) freq[c]++;
    
    priority_queue<pair<int,char>> pq;
    for (auto& p : freq) pq.push({p.second, p.first});
    
    string res;
    pair<int,char> prev = {0, '#'};
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        res += cur.second;
        if (prev.first > 0) pq.push(prev);
        cur.first--;
        prev = cur;
    }
    return res.size() == s.size() ? res : "";
}

// Ugly Number II
// LeetCode: 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
int nthUglyNumber(int n) {
    vector<int> ugly(n);
    ugly[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int next2 = ugly[i2] * 2;
        int next3 = ugly[i3] * 3;
        int next5 = ugly[i5] * 5;
        ugly[i] = min({next2, next3, next5});
        if (ugly[i] == next2) i2++;
        if (ugly[i] == next3) i3++;
        if (ugly[i] == next5) i5++;
    }
    return ugly[n - 1];
}

// Meeting Rooms II
// LeetCode: 253. Meeting Rooms II
// https://leetcode.com/problems/meeting-rooms-ii/
int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto& iv : intervals) {
        if (!pq.empty() && pq.top() <= iv[0]) pq.pop();
        pq.push(iv[1]);
    }
    return pq.size();
}

// Smallest Range Covering Elements from K Lists
// LeetCode: 632. Smallest Range Covering Elements from K Lists
// https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
vector<int> smallestRange(vector<vector<int>>& nums) {
    auto cmp = [&](auto& a, auto& b) {
        return nums[a.first][a.second] > nums[b.first][b.second];
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
    
    int mx = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        pq.push({i, 0});
        mx = max(mx, nums[i][0]);
    }
    
    vector<int> res = {0, INT_MAX};
    while (pq.size() == nums.size()) {
        auto [i, j] = pq.top(); pq.pop();
        int mn = nums[i][j];
        if (mx - mn < res[1] - res[0]) res = {mn, mx};
        if (j + 1 < nums[i].size()) {
            pq.push({i, j + 1});
            mx = max(mx, nums[i][j + 1]);
        }
    }
    return res;
}

// Kth Smallest Element in a Sorted Matrix
// LeetCode: 378. Kth Smallest Element in a Sorted Matrix
// https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
int kthSmallest(vector<vector<int>>& matrix, int k) {
    auto cmp = [&](auto& a, auto& b) {
        return matrix[a.first][a.second] > matrix[b.first][b.second];
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
    
    int n = matrix.size();
    for (int i = 0; i < n; i++) pq.push({i, 0});
    
    for (int i = 0; i < k - 1; i++) {
        auto [r, c] = pq.top(); pq.pop();
        if (c + 1 < n) pq.push({r, c + 1});
    }
    auto [r, c] = pq.top();
    return matrix[r][c];
}