Multiple Comparisons in a C++ Priority Queue

The C++ standard priority queue (std::priority_queue) is typically used with a single comparison criterion, which determines the order in which elements are stored and retrieved. However, if you need to use multiple comparisons for the elements in a priority queue, you can achieve this by providing a custom comparison function or using a custom data structure that encapsulates the comparison logic.

Here’s how you can implement a priority queue with multiple comparisons:

Using a Custom Comparison Function:

You can provide a custom comparison function or functor that encapsulates the multiple comparison criteria. This function should return true if the first element should come before the second element in the priority queue according to your custom criteria.

Here’s an example of using a custom comparison function with a priority queue of integers based on multiple criteria:

#include <iostream>
#include <queue>

struct CustomComparison {
    bool operator()(int a, int b) const {
        // Example: Sort integers in descending order of absolute value,
        // and if absolute values are the same, sort in ascending order.
        int absA = (a < 0) ? -a : a;
        int absB = (b < 0) ? -b : b;

        if (absA != absB) {
            return absA < absB;
        } else {
            return a > b;
        }
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, CustomComparison> pq;

    pq.push(5);
    pq.push(-3);
    pq.push(7);
    pq.push(-2);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

In this example, we define a custom comparison functor CustomComparison that compares integers based on their absolute values and their signs. The priority queue is declared with this custom comparison functor.

Using a Custom Data Structure:

Alternatively, you can use a custom data structure (e.g., a struct or class) to encapsulate the elements you want to store in the priority queue. Then, you can define the comparison logic within that data structure by overloading the < operator or by providing a custom comparison function within the data structure.

Here’s a simple example using a custom data structure:

#include <iostream>
#include <queue>

struct CustomData {
    int value;

    CustomData(int val) : value(val) {}

    bool operator<(const CustomData& other) const {
        // Example: Compare based on the absolute value of the 'value' member.
        int absValue = (value < 0) ? -value : value;
        int absOtherValue = (other.value < 0) ? -other.value : other.value;

        return absValue < absOtherValue;
    }
};

int main() {
    std::priority_queue<CustomData> pq;

    pq.push(CustomData(5));
    pq.push(CustomData(-3));
    pq.push(CustomData(7));
    pq.push(CustomData(-2));

    while (!pq.empty()) {
        std::cout << pq.top().value << " ";
        pq.pop();
    }

    return 0;
}

In this example, we define a CustomData structure and overload the < operator to define the comparison logic within the structure itself.

By providing a custom comparison function or using custom data structures, you can implement priority queues with multiple comparisons based on your specific requirements.