Как удалить элемент не сверху из 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

Лучшее решение — использовать std::set. Наборы предоставляют методы, которые позволяют использовать его как минимальную/максимальную кучу (или приоритетную очередь).

std::set<int> pq;

//accessing the smallest element(use as min heap)
*pq.begin();

//accessing the largest element (use as max heap)
*pq.rbegin();

Кроме того, наборы также допускают случайное удаление.

//to delete the integer '6'
auto it = pq.find(6);
pq.erase(it);

Небольшой изящный трюк для обработки удалений для очереди с приоритетом STL — используйте другую очередь с приоритетом, скажем, del_pq. Продолжайте вставлять сюда все значения удаления. Когда вы извлекаете значения из исходной очереди с приоритетом, проверьте верхнюю часть del_pq и посмотрите, хотим ли мы ее удалить. Если оно совпадает, удалите значение из исходного priority_queue.

Этот метод реализует способ ленивого удаления значений в нашей исходной очереди приоритетов. Может занимать в два раза больше памяти, но в среднем удаление и вставка остаются O(logN).

Прадип и МАШ жертвуют временем, чтобы реализовать операцию по удалению. Но если для вас важна временная сложность, я предлагаю вам использовать хэш min_heap. В хэш-таблице хранится указатель на значение, а указатели указывают на min_heap. Это означает, что вы можете потратить O(1) времени, чтобы найти значение в min_heap и O(log(n)) для удаления (просеивания или просеивания) элемента.

Обратите внимание следующий подход работает, но не является оптимизированным способом решения. Для оптимального подхода проверьте другие ответы.

Пусть вы хотите удалить 5-й элемент в priority_queue<type> Q . Затем вы можете сделать это так:

vector<type> tempQ;
int i = 0;
int n = 5;
type t;

// backup n-1 items
while(i < n-1)
{
    tempQ.push_back(Q.top());
    Q.pop();        
    i++;
}

// remove the nth item
Q.pop();

// restore the backed up items
i = 0;
while(i < n-1)
{
    t = tempQ[i++];
    Q.push(t);
}