c++ - geeksforgeeks - ¿Cómo eliminar el elemento que no está en la parte superior de la prioridad?

priority queue default order c++

Question

En mi programa necesito eliminar un elemento de una cola de prioridad que no está en la parte superior. ¿Se puede hacer eso? De lo contrario, sugiera una forma de hacerlo excepto creando su propio montón.

Answer 1

Deje que desee eliminar el quinto elemento de la priority_queue<type> Q Entonces puedes hacer esto como:

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);
}

Answer 2

La priority_queue<T> la priority_queue<T> se puede personalizar a través de la herencia. Ha protegido a los miembros c y comp que pueden ser referenciados en una clase descendiente.

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 << ", ";
      }
   }

 }

Salida:

10, 4, 3, 2

Answer 3

Pradip y MASh sacrifican el tiempo para realizar la operación de eliminación. Pero si la complejidad del tiempo es importante para ti, te sugiero que uses hash min_heap. Una tabla Hash almacena el puntero de valor y los punteros apuntan a un min_heap. Lo que significa que puede pasar O (1) tiempo para encontrar el valor en min_heap y O (log (n)) para eliminar (modificar o ajustar) el elemento.