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?
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>
{
...
};