0

I want to modify the <queue> STL so that it can find any element from the priority_queue, then delete it from the pq. The code is based on the answer by alexm from How to remove element not at top from priority_queue?

However, what I want to achieve is more complicated: the element in the priority_queue is pair<char, double>, and I want to achieve a min-heap. Thus, I modified the code as below:

#include <iostream>
#include <queue>
using namespace std;
using item_type = pair<char, double>;

template<typename T>
class custom_priority_queue : public priority_queue<T, vector<T>, greater<>> {
public:
    bool eleExist(const T& value) {
        auto it = lower_bound(this->c.begin(), this->c.end(), value);
        if (it != this->c.end())
            return true;
        else
            return false;
    }
    
    bool remove(const T& value) {
        auto it = lower_bound(this->c.begin(), this->c.end(), value);
        if (it != this->c.end()) {
            this->c.erase(it);
            make_heap(this->c.begin(), this->c.end(), this->comp);
            return true;
        }
        else {
            return false;
        }
    }
};

int main() {
    custom_priority_queue<item_type> pq;

    // use list to fill priority_queue later
    // larger number means higher priority
    initializer_list<item_type> il {
        {'A', 10},
        {'B', 12},
        {'H', 12}
    };
    // iterator through list to fill into priority_queue
    for (const auto& item : il) {
        pq.emplace(item);
    }
    
    if (pq.eleExist({'A', 10})) {
        cout << "A exists. Thus remove it" << endl;
        pq.remove({'A', 10});
    }
    else
        cout << "A doens't exist" << endl;

    // print priority_queue
    cout << "Currently in priority queue:" << endl;
    while (!pq.empty()) {
        cout << pq.top().first << ": " << pq.top().second << endl;
        pq.pop();
    }
    cout << endl;

    return 0;
}

Unfortunately, I can only use eleExist and remove functions with the full pair in my main function. What I really want to achieve is, to find element in priority_queue based on the 1st element in pair, and is able to delete the pair element based on the eleExist function. How do I modify my derived class custom_priority_queue to achieve that?

Thanks.

Heifetz_Fan
  • 439
  • 1
  • 6
  • 15
  • Consider using "lower_bound()" (O(log(n)) instead of "find()" (O(n)). Priority queues are sorted, and this in turn allows for a fast search (O(log(n))). The use of "find" degrades performance here. – Ronald Souza Nov 27 '20 at 21:10
  • Attempting to subclass `priority_queue` is completely the wrong way to go about it. The correct way to use the `priority_queue` is to implement a custom comparator. This is standard `priority_queue` functionality, see your C++ textbook for more information. – Sam Varshavchik Nov 27 '20 at 21:10
  • Hi @Sam Varshavchik, how can a comparator achieve the goal of finding and deleting ANY element from the `priority_queue`? By ANY, I mean the element might not be at the top of the `priority_queue`. Can you be specific? Thanks. – Heifetz_Fan Nov 27 '20 at 21:22
  • Thanks @RonaldSouza. I modified codes in my question based on your suggestion. – Heifetz_Fan Nov 27 '20 at 21:26
  • @RonaldSouza Priority queue is not fully sorted, as it's a heap structure. lower_bound on a heap won't work correctly. – rustyx Nov 27 '20 at 21:53
  • 1
    It looks like you could use a sorted `vector` instead of a `priority_queue`. Then you can search in it quickly using `lower_bound`. But! Removing one element in the middle of a `vector` is an O(N) operation as all remaining elements have to be moved. If you remove frequently, then a binary tree (`std::map`) might be more efficient. Benchmark to be sure. – rustyx Nov 27 '20 at 21:57
  • @rustyx True. Thank you. But still, to use "find" in a heap structure does not seem to be the way to go. – Ronald Souza Nov 28 '20 at 21:52
  • @rustyx +1 for your suggestion. – Ronald Souza Nov 28 '20 at 21:53

1 Answers1

1

Instead of looking for exact value with std::find, you might use the version with predicate (std::find_if):

template<typename T>
class custom_priority_queue : public std::priority_queue<T, std::vector<T>, std::greater<>> {
public:
    template <typename Pred>
    bool contains_if(Pred pred) const {
        auto it = std::find_if(this->c.begin(), this->c.end(), pred);
        return it != this->c.end();
    }
    
    template <typename Pred>
    bool remove_if(Pred pred) {
        const auto old_size = this->size();
        this->c.erase(std::remove_if(this->c.begin(), this->c.end(), pred), this->c.end());
        if (old_size == this->size()) return false;
        std::make_heap(this->c.begin(), this->c.end(), this->comp);
        return true;
    }
};

Demo

Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • Thanks @Jarod42. What's the time complexity of using `find_if` and `remove_if`combined w/ `erase` then? Based on https://en.cppreference.com/w/cpp/algorithm/find, all 3 function should be `O(n)`? – Heifetz_Fan Dec 01 '20 at 12:35
  • Yes. all are `O(n)`. – Jarod42 Dec 01 '20 at 13:12
  • Thanks again @Jarod42. Is there a way of realizing what I want in `O(logN)`: 1) I don't need a fully-sorted data structure for every step. Instead, I only care the smallest element (each element is a `pair`, comparison is based on `pair.second`); 2) However, I frequently search elements in the data structure based on `pair.first`, and need to delete that element based on my search. – Heifetz_Fan Dec 01 '20 at 13:19