Search code examples
c++data-structuresheappriority-queue

C++ priority_queue with custom comparator and removal of any item


I am working on a solution with min heap which apart from custom comparator requires support of removal of any element. A fully custom heap impl is one way to go. But I wanted to rely on C++ STL for desired operations.
C++ documentation and StackOverflow answer here pointed me to use a custom class and overload custom remove method. I also overloaded custom comparator in the same class.

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

    return false;
  }

  bool operator()(const pair<int, int> &a, const pair<int, int> &b)
  {
    cout << "Custom comparator called" << endl;  <----------- Never called
    return a.second > b.second;
  }
};

Consumption of the custom heap looks something like:

custom_priority_queue_MinHeap<pair<int, int>> minHeap;
minHeap.push({0, 10});
minHeap.push({1, 5});
minHeap.push({2, 15});

while(!minHeap.empty())
{
    pair<int, int> p = minHeap.top();
    minHeap.pop();
    cout << p.first << " " << p.second << endl;
}

When run on Ideone, minHeap push is not working as expected. It flashes below output:

2 15
1 5
0 10    

The correct output should be:

1 5
0 10  
2 15      

The () comparator overload is never called which seems to be the culprit. Elements are getting popped in the order they were inserted. Interestingly, remove function is working fine.

Question(s):
Is it possible to fully rely on C++ priority_queue STL to achieve desired operations, i.e. custom comparator with support of removal of any element? If yes, is there anything I am missing in the above implementation?


Solution

  • Thanks PaulMcKenzie for pointing me in right direction! The issue was that priority_queue in STL is three parameter class. My impl was missing the third compare class parameter.
    Below change worked fine. Ideone link

    class Comp
    {
    public:
        bool operator()(const pair<int, int> &a, const pair<int, int> &b)
        {
            cout << "Custom comparator called" << endl;
            return a.second > b.second;
        }
    };
    
    template<typename T>
    class custom_priority_queue_MinHeap : public std::priority_queue<T, std::vector<T>, Comp>
    {
        ...
    };