Heap and Priority Queue

1. Introduction to Heap and Priority Queue
2. What are the applications of Heap and Priority Queue?
3. Heap in C++ standard library
4. Priority Queue in C++ standard library
- 4.1. Minimum Priority Queue
5. The Applications of Priority Queues
6. References

1 Introduction to Heap and Priority Queue

A heap is a tree-based data structure that adheres to the heap property: in a max heap, any parent node's key (value) is greater than or equal to the keys of its children. Conversely, in a min heap, the key of a parent node is less than or equal to the keys of its children.

For more details, refer to Wikipedia: Heap (data structure).

A priority queue is an abstract data type similar to a regular queue or stack, where each element has an associated priority. Elements with higher priority are served before those with lower priority.

For more details, refer to Wikipedia: Priority queue.

Although they are conceptually different, priority queues are often referred to as heaps because they are commonly implemented using heaps.

The binary heap is a data structure that efficiently supports the basic priority queue operations. It allows O(1) performance for accessing the root, O(log n) for insertions and deletions, and O(n) for initially building the heap from a set of n elements.

Note that the time complexity to build a heap is O(n log n) using a top-down approach, whereas a bottom-up approach achieves O(n).

2 What are the applications of Heap and Priority Queue?

In a heap, the highest (or lowest) priority element is always stored at the root, making it partially ordered. This structure is useful when it is necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be interspersed with removals of the root node.

A heap facilitates the efficient identification of the kth largest (or smallest) element in an array.

Priority queues are used in practical scenarios where customers with urgent service requirements are prioritized over those who arrived earlier. For example, customers with fewer items might receive preference at licensing centers, reducing the average waiting time for all customers in the queue.

Priority queues implemented with heaps are crucial in advanced graph algorithms like Prim's algorithm, Dijkstra's algorithm, Huffman coding, and Breadth-First Search (BFS).

In security-focused and embedded systems, such as the Linux Kernel, heap sort is employed. This sorting algorithm uses the heap data structure and is an effective in-place sorting method with a worst-case time complexity of O(n log n).

Heaps are also used in a variety of applications, such as reducing round-off error in numerical computations, summing powers in number theory, A* search algorithms, Bayesian spam filters, and for load balancing and scheduling.

3 Heap in C++ standard library

In C++ standard library, the heap data structure can be implemented using a range with the help of the <algorithm> header. The functions provided within this header, such as std::make_heap, std::push_heap, std::pop_heap, std::sort_heap, and std::is_heap, allow us to manage heaps on any random-access range, like arrays or std::vector.

#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;

void printv(string_view s, const vector<int>& v)
{
    cout << s << ":\t";
    for (int i : v)
        cout << i << " ";
    cout << "\n";
}

int main()
{
    vector<int> v(7);
    iota(v.begin(), v.end(), 1);
    random_shuffle(v.begin(), v.end());
    printv("shuffled vector", v);

    make_heap(v.begin(), v.end());
    printv("initial max heap", v);

    pop_heap(v.begin(), v.end());
    v.pop_back();
    printv("max heap after pop", v);

    v.push_back(9);
    push_heap(v.begin(), v.end());
    printv("max heap after push", v);
}

Output:

shuffled vector:        5 4 2 7 1 6 3
initial max heap:       7 5 6 4 1 2 3
max heap after pop:     6 5 3 4 1 2
max heap after push:    9 5 6 4 1 2 3

The function std::make_heap converts the given range to a heap. The heapified vector (7 5 6 4 1 2 3) represents the maximum binary heap:

     7
   /   \
  5     6
 / \   / \
4   1 2   3

The function std::pop_heap moves the maximum element at the end for deletion with std::pop_back from the vector. After insertion with std::push_back at the end of the vector, std::push_heap arranges the heap accordingly.

Why is the heap a maximum heap by default in C++ standard library? It is because this convention aligns with the way std::sort sorts elements in ascending order by default. When std::sort_heap is called on a max heap, it results in a range sorted in ascending order, which is consistent with the default behavior of std::sort.

#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    vector<int> v(7);
    iota(v.begin(), v.end(), 1);
    random_shuffle(v.begin(), v.end());

    make_heap(v.begin(), v.end());

    sort_heap(v.begin(), v.end());
}

The std::sort_heap function works by repeatedly applying std::pop_heap, which moves the largest element to the end of the range and then shrinks the range by one. This process is repeated until the entire range is sorted in ascending order, with the smallest element at the front and the largest at the end.

Here is a conventional way to represent the sort_heap() function:

template
void sort_heap(RandIter start, RandIter end)
{
    while (start != end)
        std::pop_heap(start, end--);
}

4 Priority Queue in C++ standard library

The std::priority_queue in C++ is a type of container adaptor, built on the top of the maximum heap and use an array or vector as an internal structure.

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

int main()
{
    priority_queue<int> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);

    cout << "size: " << pq.size() << "\n";
    cout << "top: " << pq.top() << "\n";
    for (cout << "elements: "; !pq.empty(); pq.pop())
        cout << pq.top() << " ";
    cout << "\n";
}

Output:

size: 3
top: 3
elements: 3 2 1

The priority_queue provides several constructors, including one that accepts a range defined by two iterators and another that allows for a custom comparator and an initial container. The following code demonstrates the usage of the constrcutors to initilize priority queues from another container like std::vector.

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

int main()
{
    auto printq = [](auto& pq) {
        for (cout << "pq: "; !pq.empty(); pq.pop())
            cout << pq.top() << " ";
        cout << "\n";
    };

    vector<int> v {1,2,3};

    priority_queue<int> pq1(v.begin(), v.end());
    printq(pq1);

    priority_queue<int> pq2(less<int>(), v);
    printq(pq2);
}

Output:

pq: 1 2 3
pq: 1 2 3

4.1 Minimum Priority Queue

As previously stated, a priority queue is by default maximum priority queue. So, how can we create a minimum priority queue? There are different ways, such as to use std::greater as the comparison function. (The default comparison function is std::less)

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

int main()
{
    auto printq = [](auto& pq) {
        for (cout << "pq: "; !pq.empty(); pq.pop())
            cout << pq.top() << " ";
        cout << "\n";
    };

    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);

    printq(pq);
}

Output:

pq: 1 2 3

We can also obtain a minimum priority queue by inserting values with their opposite sign, so that the largest element becomes the smallest. When popping elements, we need to negate the value again to retrieve the original value. This method can be practical for simple data types like integers, but it's not suitable for all data types or situations. It's also important to remember that this approach only works when all the values are of the same sign to begin with.

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

int main()
{
    auto printq = [](auto& pq) {
        for (cout << "pq: "; !pq.empty(); pq.pop())
            cout << -pq.top() << " ";
        cout << "\n";
    };

    priority_queue<int> pq;
    pq.push(-2);
    pq.push(-1);
    pq.push(-3);
    printq(pq);
}

Output:

pq: 1 2 3

Besides, we can define a custom comparator by creating a functor - a class or struct with the operator() overloaded. This allows us to specify the rules for the priority within the std::priority_queue.

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

struct compare {
    bool operator()(const int& lhs, const int& rhs) {
        return lhs > rhs;
    }
};

int main()
{
    auto printq = [](auto& pq) {
        for (cout << "pq: "; !pq.empty(); pq.pop())
            cout << pq.top() << " ";
        cout << "\n";
    };

    priority_queue<int, vector<int>, compare> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);
    printq(pq);
}

Output:

pq: 1 2 3

Using a lambda expression is another way to define a custom comparator. We would use decltype to deduce the type of the lambda for the template argument and pass the lambda directly to the constructor of the std::priority_queue.

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

int main()
{
    auto printq = [](auto& pq) {
        for (cout << "pq: "; !pq.empty(); pq.pop())
            cout << pq.top() << " ";
        cout << "\n";
    };
    auto cmp = [](const int& lhs, const int& rhs) {
        return lhs > rhs;
    };

    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    pq.push(2);
    pq.push(1);
    pq.push(3);
    printq(pq);
}

Output:

pq: 1 2 3

Since C++20, stateless lambdas (those without captures) are default constructible, which simplifies their use as template parameters. We can declare a std::priority_queue with a lambda directly in the decltype as the third template parameter.

priority_queue<int, vector<int>, decltype([](const int& lhs, const int& rhs) {
    return lhs > rhs;
})> pq;

5 The Applications of Priority Queues

A priority queue is ideal for scenarios where we need to efficiently access the maximum or minimum value from a collection of elements. It ensures that the highest or lowest priority element can be accessed in constant time.

In the context of the problem 1845. Seat Reservation Manager, maintaining a minimum priority queue allows for the efficient retrieval of the smallest available seat number. The top of the queue represents the seat with the smallest number, which is the next seat to be reserved.

class SeatManager {
    priority_queue<int, vector<int>, greater<int>> seats;
public:
    SeatManager(int n) {
        for (int i = 1; i <= n; i++)
            seats.push(i);
    }

    int reserve() {
        int num = seats.top();
        seats.pop();
        return num;
    }

    void unreserve(int seatNumber) {
        seats.push(seatNumber);
    }
};

Heap sort is a sorting technique based on the binary heap data structure. It is similar to selection sort that it repeatedly selects the maximum element and moves the element to the end of the list.

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

int main()
{
    vector<int> v {9, 11, 3, 6, 1};

    make_heap(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        pop_heap(v.begin(), v.end() - i);

    for (int i: v)
        cout << i << " ";
    cout << "\n";
}

Output:

1 3 6 9 11

By performing the action of moving the maximum element to the end of the vector and then heapifying the remaining elements, we can find the kth largest element in the array. This is also one of the typical usages of heap / priority queue.

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

int main()
{
    int k = 3;
    vector<int> v {9, 11, 3, 6, 1};

    priority_queue<int> pq(v.begin(), v.end());
    while (--k)
        pq.pop();
    cout << "The 3rd maximum element = " << pq.top() << "\n";
}

Output:

The 3rd maximum element = 6

Take 973. K Closest Points to Origin as an example, using a minimum priority queue, we can store all the given points, and the results will be the first k points at the top. Alternatively, we can use a maximum priority queue and keep its size at most k. Each time we push a point, if the size of the queue becomes larger than k, we pop the top element, which is the (k+1)th largest element. Eventually, the points remaining in the queue are the results.

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<vector<int>> pq;
    for (auto& p: points) {
        pq.push({p[0] * p[0] + p[1] * p[1], p[0], p[1]});
        if (pq.size() > k)
            pq.pop();
    }

    vector<vector<int>> res;
    while (!pq.empty()) {
        vector<int> el = pq.top();
        res.push_back({el[1], el[2]});
        pq.pop();
    }
    return res;
}

The problem 1985. Find the Kth Largest Integer in the Array is another example. We can use either a maximum priority queue to find and pop the first k largest elements, or like the following, use a minimum priority queue with a size not larger than k, so that to keep only the kth largest elements, and the result will be at the top. In order to compare integer strings correctly, we need to prepend an integer indicating their length to the strings, creating a pair to serve as an element in the queue.

string kthLargestNumber(vector<string>& nums, int k) {
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
    for (auto& n : nums) {
        pq.push({n.size(), n});
        if (pq.size() > k)
            pq.pop();
    }
    return pq.top().second;
}

Similarly for the problem 703. Kth Largest Element in a Stream, we may simply maintain a minimum priority queue with size not larger than k. Each time we add a value, we can remove the (k+1)th largest value if the queue exceeds size k, ensuring the top of the queue is the kth largest value.

class KthLargest {
    int capacity;
    priority_queue<int, vector<int>, greater<int>> pq;
public:
    KthLargest(int k, vector<int>& nums) {
        capacity = k;
        for (int i : nums) {
            pq.push(i);
            if (pq.size() > capacity)
                pq.pop();
        }
    }

    int add(int val) {
        pq.push(val);
        if (pq.size() > capacity)
            pq.pop();
        return pq.top();
    }
};

Sometimes it is necessary to fetch the top of the priority queue multiple times, for example 1046. Last Stone Weight, we create a maximum priority queue for the stones, then pop the heaviest two to be smashed and push back the remaining if there is any. Continue until only one stone remains or the queue is empty.

int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> pq(stones.begin(), stones.end());
    while (pq.size() > 1) {
        int y = pq.top();
        pq.pop();
        int x = pq.top();
        pq.pop();
        if (y - x)
            pq.push(y - x);
    }
    return pq.empty()? 0: pq.top();
}

Priority queue of non primitive type or customized structure or class is often needed too, for example the problem "1985. Find the Kth Largest Integer in the Array" that we saw previously. In problems like 1094. Car Pooling, we track passenger changes at each location. For each trip vector, we construct two pairs: one for the start location with the number of passengers to pick up, and the other for the end location with the number of passengers to drop off, represented as a negative number. These pairs are pushed into a minimum priority queue. By processing the queue, we can determine if the carpool is feasible by ensuring the number of passengers never exceeds the available seats.

bool carPooling(vector<vector<int>>& trips, int capacity) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (auto t: trips) {
        pq.push({t[1], t[0]});
        pq.push({t[2], -t[0]});
    }
    int num = 0;
    while (!pq.empty()) {
        num += pq.top().second;
        pq.pop();
        if (num > capacity)
            return false;
    }
    return true;
}

In problems like 502. IPO, where multiple priorities exist, we can either use a custom class or create multiple standard priority queues. Initially, a minimum priority queue, minCap, contains all projects, sorted by capital. A maximum priority queue, maxPro, holds projects that meet the current capital criteria, sorted by profit. In each iteration, we move eligible projects from minCap to maxPro and then select the most profitable project from maxPro to update the company's capital.

int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minCap;
    for (int i = 0; i < capital.size(); i++)
        minCap.push({capital[i], profits[i]});

    priority_queue<pair<int, int>> maxPro;
    while (k) {
        while (!minCap.empty() && minCap.top().first <= w) {
            auto [c, p] = minCap.top();
            minCap.pop();
            maxPro.push({p, c});
        }
        if (maxPro.empty())
            break;
        w += maxPro.top().first;
        maxPro.pop();
        k--;
    }
    return w;
}

In 1383. Maximum Performance of a Team, we aim to maximize performance, but the team's performance is limited by the minimum efficiency among its engineers. To address this challenge, we first sort the engineers by efficiency in descending order. As we select engineers one by one, the newly selected one will have the lowest efficiency, and we maintain a minimum priority queue based on speed to keep track of the currently selected engineers. When selecting a new engineer, we may need to remove the one with the lowest speed from the queue to calculate and possibly update the team's performance.

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
    const int mod = 1e9 + 7;
    vector<pair<int, int>> engineers;
    for (int i = 0; i < n; i++)
        engineers.push_back({efficiency[i], speed[i]});

    sort(engineers.rbegin(), engineers.rend());

    priority_queue<int, vector<int>, greater<int>> pq;
    long long sum = 0, res = 0;
    for (auto& [ef, sp]: engineers) {
        pq.push(sp);
        sum += sp;
        res = max(res, sum * ef);
        if (pq.size() >= k) {
            sum -= pq.top();
            pq.pop();
        }
    }
    return res % mod;
}

In 1675. Minimum Deviation in Array, we note that after any number of operations, a number's minimum possible value is odd, and its maximum possible value is even. We create a maximum priority queue with the maximum possible values of all elements and maintain a separate variable for the minimum element in the queue. The current deviation is the difference between the top of the queue and this minimum value. We then perform operations on the top element if it is even: we pop it, push the halved element, and update the minimum and deviation as needed.

int minimumDeviation(vector<int>& nums) {
    priority_queue<int> pq;
    int qmin = INT_MAX;
    for (int n : nums) {
        if (n % 2 == 1)
            n *= 2;
        pq.push(n);
        qmin = min(qmin, n);
    }

    int res = pq.top() - qmin;
    while (pq.top() % 2 == 0) {
        int n = pq.top() / 2;
        pq.pop();
        pq.push(n);
        qmin = min(qmin, n);
        res = min(res, pq.top() - qmin);
    }

    return res;
}

Priority queues access the top element, which is either the maximum or the minimum. When we need to access the median, as in 295. Find Median from Data Stream, we can divide the elements into two priority queues: a maximum priority queue for the smaller half and a minimum priority queue for the larger half. When adding a new value, we place it in the appropriate queue - either the large half or the small half - and ensure the size difference between the two queues is not greater than 1. The median is then either the top of the larger queue or the average of the tops of both queues if they are the same size.

class MedianFinder {
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int>> large;

public:
    void addNum(int num) {
        if (!large.empty() && num >= large.top())
            large.push(num);
        else
            small.push(num);

        if (large.size() > small.size() + 1) {
            small.push(large.top());
            large.pop();
        }
        else if (small.size() > large.size() + 1) {
            large.push(small.top());
            small.pop();
        }
    }

    double findMedian() {
        if (large.size() > small.size())
            return large.top();
        else if (small.size() > large.size())
            return small.top();
        double res = large.top() + small.top();
        return res / 2.0;
    }
};

In 767. Reorganize String, when rearranging the characters, we should choose a non-repeating and the most frequent character so that it has the best opportunity to be delimited by another character. Therefore, we create a maximum priority queue with the frequency of the characters as the priority, and a 'prev' queue to store the character just added (to avoid choosing it repeatedly). In each iteration, the top of the priority queue becomes the next character in the result. If the character has more occurrences, we place it in the 'prev' queue. The character in the 'prev' queue will not be a candidate this time, but it will be for the next.

string reorganizeString(string s) {
    unordered_map<char, int> freq;
    for (char c : s)
        freq[c]++;

    priority_queue<pair<int, char>> pq;
    for (auto [ch, count]: freq)
        pq.push({count, ch});

    queue<pair<int, char>> prev;
    string res{};

    while (!pq.empty() || !prev.empty()) {
        if (pq.empty())
            return "";

        auto [count, ch] = pq.top();
        pq.pop();
        count--;
        res += ch;

        if (!prev.empty()) {
            pq.push(prev.front());
            prev.pop();
        }
        if (count)
            prev.push({count, ch});
    }
    return res;
}

In 2542. Maximum Subsequence Score, there is a similar challenge to what was seen in '1383. Maximum Performance of a Team'. We aim to maximize the score, but the score of a subsequence is limited by the minimum of the selected elements from the 'nums2' vector. Therefore, we pair each element from 'nums1' with the corresponding element from 'nums2' and sort these pairs. As we process pairs one by one, the selected number from 'nums2' will have the minimum value, and we maintain a maximum priority queue of numbers from 'nums1'. Each time we process a pair, we add the 'nums1' value to the maximum priority queue and update the score using the minimum 'nums2' value.

long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<pair<int, int>> pairs;
    for (int i = 0; i < nums1.size(); i++)
        pairs.push_back({nums1[i], nums2[i]});

    sort(pairs.begin(), pairs.end(), [](const auto& lhs, const auto&rhs) {
        return lhs.second > rhs.second;
    });

    priority_queue<int, vector<int>, greater<int>> pq;
    long long res = 0, sum = 0;
    for (const auto& p: pairs) {
        sum += p.first;
        pq.push(p.first);
        if (pq.size() >= k) {
            res = max(res, sum * p.second);
            sum -= pq.top();
            pq.pop();
        }
    }
    return res;
}

Priority queues are also frequently used for load balancing and task scheduling. In 1834. Single-Threaded CPU, We create two priority queues: the first is a waiting queue containing all unfinished tasks, with the task having the earliest enqueue time at the top. The second queue holds tasks ready to be executed, with the task having the shortest processing time at the top. At each tick, we move tasks from the waiting queue to the ready queue if their enqueue time is less than or equal to the current time. Then, we process the task at the top of the ready queue. The time (tick) is updated by adding the processing time of the next task in the ready queue if it's not empty; otherwise, it's set to the enqueue time of the next task in the waiting queue.

vector<int> getOrder(vector<vector<int>>& tasks) {
    for (int i = 0; i < tasks.size(); i++) {
        tasks[i].push_back(i);
    }
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>>
        wait(tasks.begin(), tasks.end());

    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> ready;
    long long time = 0;
    vector<int> res;

    while (!wait.empty() || !ready.empty()) {
        while (!wait.empty() && time >= wait.top()[0]) {
            ready.push({wait.top()[1], wait.top()[2]});
            wait.pop();
        }

        if (ready.empty()) {
            time = wait.top()[0];
        }
        else {
            res.push_back(ready.top()[1]);
            time += ready.top()[0];
            ready.pop();
        }
    }
    return res;
}

And, in 1882. Process Tasks Using Servers, we create two priority queues. The first contains servers ready to process tasks, with the server having the minimum weight at the top. The second contains servers busy processing tasks, with the server having the minimum remaining processing time at the top. In each loop, the time (tick) is set to either the index of the task or the nearest future time when a server becomes free. Servers in the busy queue that have finished their tasks are popped and pushed to the ready queue. The server used to process the next task is taken from the top of the ready queue.

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
    //ready queue priority: weight, index
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ready;
    for (int i = 0; i < servers.size(); i++) {
        ready.push({servers[i], i});
    }

    //busy queue priority: time being free, index
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy;
    int time = 0;
    vector<int> res;

    for (int i = 0; i < tasks.size(); i++) {
        if (ready.empty())
            time = busy.top().first;
        else
            time = max(time, i);

        while (!busy.empty() && busy.top().first <= time) {
            int idx = busy.top().second;
            busy.pop();
            ready.push({servers[idx], idx});
        }

        int idx = ready.top().second;
        ready.pop();
        busy.push({time + tasks[i], idx});
        res.push_back(idx);
    }
    return res;
}

Similarly, in 621. Task Scheduler, we create two priority queues. The first contains tasks ready to be processed, with the task having the highest frequency at the top. The second contains tasks cooling down that need further processing, with the task having the shortest remaining cooling time at the top. In each loop, we tick the time. If the ready queue is empty (CPU has to idle), the time advances to when the next task is ready. Otherwise, the task with the highest frequency in the ready queue is processed, and if it requires further processing, it is moved to the cooling queue. If the task at the top of the cooling queue has finished cooling down, it is moved back to the ready queue. The final time will be the result.

int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26);
    for (char c: tasks)
        freq[c - 'A']++;

    priority_queue<int> ready;
    for (int f : freq) {
        if (f)
            ready.push(f);
    }

    int time = 0;
    queue<pair<int, int>> wait; //time, freq left

    while (!ready.empty() || !wait.empty()) {
        time++;
        if (ready.empty())
            time = wait.front().first;
        else {
            int left = ready.top() - 1;
            ready.pop();
            if (left > 0)
                wait.push({time + n, left});
        }
        if (!wait.empty() && wait.front().first == time) {
            ready.push(wait.front().second);
            wait.pop();
        }
    }

    return time;
}

There is an O(1) solution for this problem, by deducing a formula. Consider the example:

tasks = ['A', 'A', 'A', 'B', 'B', 'B', 'C', 'D'], n = 2

Maximum frequency is 3 and maximum occuring task is A and B. The solution will be:

['A' -> 'B' -> 'C'] -> ['A', 'B', 'D'] -> ['A', 'B']

where the total time is 3 + 3 + 2 = 8.

Notice that the cycle A -> B -> other_task repeats 2(maximum frequency - 1) times and then A -> B occurs. A and B are the maximum frequency elements which makes the cycle of length 3(n + 1). We conclude that total time is cycle length * (maximum_frequency - 1) + number of maximum frequency tasks that are left, i.e:

total_time = (n + 1) * (max_freq - 1) + count_max_freq_tasks

The code:

int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26);
    int maxFreq = 0;
    for (char c : tasks) {
        freq[c - 'A']++;
        maxFreq = max(maxFreq, freq[c - 'A']);
    }

    int cntMaxFreq = 0; // number of tasks with the maximum count
    for (int n : freq) {
        if (n == maxFreq)
            cntMaxFreq++;
    }

    return max((int)tasks.size(), (n + 1) * (maxFreq - 1) + cntMaxFreq);
}

Prim's algorithms is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. A priority queue data structure is used in a variation of the algorithm, leading to a better time complexity of O(E log V). The problem 1584. Min Cost to Connect All Points is an example. We maintain a priority queue of all the edges, with their costs (Manhattan distance between two points/vertices) as the priority. Starting from the first vertex, we add all the edges with one endpoint being this vertex to the priority queue. Each time, we add the edge with the minimum weight to the minimum spanning tree and select the next vertex to process. We continue until all vertices are connected. The result is the sum of the weights of the edges in the tree.

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<bool> marked(n);

    // pair: <weight of edge, index of (peer) vertex>
    priority_queue<pair<int, int>> pq;

    int i = 0; // index
    int res = 0; // total cost
    int edges = 0; // number of edges in MST currently
                   //
    while (++edges < n) {
        marked[i] = true;

        for (int j = 0; j < n; j++) {
            if (marked[j]) continue;
            pq.push({-abs(points[i][0] - points[j][0])
                     -abs(points[i][1] - points[j][1]),
                     j});
        }

        while (marked[pq.top().second])
            pq.pop();
        res -= pq.top().first;
        i = pq.top().second;
        pq.pop();
    }

    return res;
}

Note that there are many different ways to solve minimum spanning tree problems, such as Kruskal's algorithm. I will talk about those in another article.

Dijkstra's algorithm is used for finding the shortest paths between nodes in a weighted graph. A priority queue is often used to optimize the algorithm instead of a generic queue. In the problem 787. Cheapest Flights Within K Stops, we build an adjacency list of all the nodes, where an edge is a pair specifying the cost from this node to the adjacent node. We then create a priority queue for paths starting from the source, where a path entry contains the cost from the source node, the current destination node number, and the number of stops, with cost as the priority. In each step, we get the path with the least cost from the queue, skip paths that exceed the stop limit or form loops, and update it with the adjacent node information. If the current node is the destination, that path cost will be the result.

int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
    // edge pair: <to node, price>
    vector<vector<pair<int, int>>> adj(n);
    for (auto& f : flights)
        adj[f[0]].push_back({f[1], f[2]});

    // path vector: cost, to node, number of stops
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    pq.push({0, src, 0});

    vector<int> noStops(n, INT_MAX);
    noStops[src] = 0;

    while (!pq.empty()) {
        int cost = pq.top()[0];
        int curr = pq.top()[1];
        int stop = pq.top()[2];
        pq.pop();

        if (noStops[curr] < stop)
            continue;
        noStops[curr] = stop;

        if (curr == dst) // k stops in between, dst = k + 1 th stop
            return cost;

        if (stop > k)
            continue;

        for (auto &x : adj[curr]) {
            pq.push({cost + x.second, x.first, stop + 1});
        }
    }
    return -1;
}

Note that there are variaous of other ways to solve shortest path problems, such as Bellman-Ford algorithm. I will talk about those in some other article.

I hope this article have helped you understand Priority Queue better. If you are interested in practicing more problem solving, please check out LeetCode - Heap (Priority Queue) tag.

6 References

Author: Winfred Lu

Created: 2024-04-11 Thu 17:03

Validate

Winfred C. H. Lu

Thursday, April 11, 2024