Understanding Priority Queue

A priority queue differs from a standard queue as it organizes elements based on their priority rather than insertion order. Imagine a scenario where critical tasks always take precedence over routine ones. Within critical tasks, they might be further prioritized by urgency level. The queue automatically maintains this ordering, ensuring the highest priority elements are always at the front. When a new high-priority task arrives, it's inserted according to its priority level, not based on when it arrived.

Creating Priority Queues

priority_queue<int, vector<int>, less<>> max_heap;
priority_queue<int, vector<int>, greater<>> min_heap;

The first template parameter specifies the data type stored in the queue. The second parameter is the container type, which must be a sequence container implemented as an array (like vector or deque), but not list. The STL defaults to vector if unspecified. The third parameter is crucial and determines the ordering behavior.

Less and Greater Comparators

For basic data types like int, string, or double, you can directly use less<> or greater<> as the third parameter. Understanding which creates a max-heap and which creates a min-heap can be confusing: - less<> implements a max-heap (largest elements have highest priority) - greater<> implements a min-heap (smallest elements have highest priority) The confusion arises because the priority queue returns elements from the "top" (front) of the container, not the end. With less<>, elements are sorted in ascending order, so the largest element is at the end of the container but becomes the top element in the priority queue. Similarly, with greater<>, elements are sorted in descending order, making the smallest element the top element.

Functors

A functor (function object) is a class that overloads the operator() method, allowing it to be used as if it were a function. This approach is commonly used in STL algorithms like sort, where you provide a custom comparison function.

Example: Finding Top K Frequent Elements

For this problem, we need to determine whether a max-heap or min-heap is appropriate. The goal is to find the most frequent elements, which might initially suggest using a max-heap. However, in a max-heap, the highest priority elements (most frequent) would be removed first, which is the opposite of what we want. Instead, we use a min-heap with a size limit of k. This allows us to keep the k most frequent elements while removing less frequent ones as we process the data. Since we're working with pairs of (element, frequency), we need a custom comparator functor:

class FrequencyComparator {
public:
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
};

The solution involves using a hash map to count frequencies first:

vector<int> findTopKFrequent(vector<int>& nums, int k) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, FrequencyComparator> freq_queue;
    unordered_map<int, int> frequency_map;
    
    // Count frequencies
    for (int num : nums) {
        frequency_map[num]++;
    }
    
    // Maintain a min-heap of size k
    for (auto& entry : frequency_map) {
        freq_queue.push(entry);
        if (freq_queue.size() > k) {
            freq_queue.pop();
        }
    }
    
    // Extract elements
    vector<int> result;
    while (!freq_queue.empty()) {
        result.push_back(freq_queue.top().first);
        freq_queue.pop();
    }
    
    return result;
}

The implementation is straightforward once you understand whether to use a max-heap or min-heap for the specific problem. The rest follows logically from there.