Как удалить элемент не сверху из priority_queue?
В моей программе мне нужно удалить элемент из очереди с приоритетами, который находится не сверху. Это может быть сделано? Если нет, предложите, пожалуйста, способ сделать это, кроме создания собственной кучи.
Решение
Стандарт priority_queue<T> можно настроить через наследование. Он защищал членов c а также comp на которые можно ссылаться в классе-потомке.
template<typename T>
class custom_priority_queue : 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;
}
else {
return false;
}
}
};
void main()
{
custom_priority_queue<int> queue;
queue.push(10);
queue.push(2);
queue.push(4);
queue.push(6);
queue.push(3);
queue.remove(6);
while (!queue.empty())
{
std::cout << queue.top();
queue.pop();
if (!queue.empty())
{
std::cout << ", ";
}
}
}
Выход:
10, 4, 3, 2
Другие решения
Прадип и МАШ жертвуют временем, чтобы осуществить операцию удаления.
Но если вам важна временная сложность, я предлагаю вам использовать хеш min_heap.
Хэш-таблица хранит указатель значения, а указатели указывают на min_heap.
Это означает, что вы можете потратить O (1) время, чтобы найти значение в min_heap и O (log (n)), чтобы удалить (sift-up или sift down) элемент.
Пусть вы хотите удалить 5-й элемент в priority_queue<type> Q ,
Тогда вы можете сделать это следующим образом:
vector<type> tempQ;
int i=0;
int n=5;
type t;
while(i<n-1)
{
tempQ.push_back(Q.top());
Q.pop();
i++;
}
Q.pop();
i=0;
while(i<n-1)
{
t=tempQ[i++];
Q.push(t);
}