How to Remove Element Not at Top from Priority_Queue

Deleting element in priority queue other than top element in C++

Is there any inbuilt function for deleting a given element (other than top element) in priority queue class of C++ STL?

No.

If not how to delete it in O(log n)?

By using another container. std::set is the simplest compromise. A custom heap implementation may be more optimal.

priority_queue - delete not a top elements

Maybe implementing Priority-queue using LINK-LIST can be a good ideal. By that, you can search for the element and delete it as normal link list. Hope this can be helpful for you.

STL Priority Queue - deleting an item

I had the exact same scenario once and did the following:

the structure I kept in std::priority_queue contained only the time to sort by and an index to a std::vector<Handler> (in my case Handler was boost::function, but could as well be pointer to interface or function)
when adding a timer, I'd find a free index in the vector of handlers¹ and store the handler at that index. Store the index and the time in the priority_queue. Return the index to the client as token to cancel
to cancel a timer, pass the index received when adding it. Clear the handler at that index (for boost::function call clear(), if using pointers, set it to zero)
when it's time to callback a timer, get its handler index from the priority queue and check the handlers vector - if the handler at that position is empty()/NULL, the timer has been canceled. Mark that handler index as free².

¹ To make finding a free index fast, I used a separate std::stack of indices. When adding a timer and that stack is empty, add at the end of vector; otherwise pop the top index and use it.

² Here's the point when you push the index to the free indices stack

The whole thing is somewhat tricky and error-prone, especially if your timer callbacks need to add or cancel timers. Here's a link to my canceling timer class described above, this code is public domain

How to remove element from list with a corresponding priority queue?

So here is the why Arch's code was not quite working, and I figure it is probably better to just show it to the OP. The missing link was the equality operator ==() for removal from the std::list<>. Without that std::list<T>::remove() has no way to compare whether the object sent is the one being examined for removal.

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
#include <queue>
#include <iomanip>
#include <ctime>
using namespace std;

// my rabbit (I don't have yours).
struct Rabbit
{
    Rabbit(int weight=0, int size=0)
       : weight(weight), size(size) {};

    int weight;
    int size;

    // needed for std::list<>::remove()
    bool operator ==(const Rabbit& other)
    {
        return weight == other.weight
            && size == other.size;
    }
};

// write to output stream
std::ostream& operator <<(std::ostream& os, const Rabbit& rabbit)
{
    os << '[' << setw(2) << rabbit.weight << ',' << setw(2) << rabbit.size << ']';
    return os;
}

// functor for comparing two rabbits by address
struct CompareRabbitPtrs
{
    bool operator ()(const Rabbit* left, const Rabbit* right)
    {
        return right->weight < left->weight ||
              (right->weight == left->weight && right->size < left->size);
    }
};

// some typedefs to make life a little easier. first the list
typedef std::list<Rabbit> RabbitList;

// now the priority_queue
typedef std::priority_queue<Rabbit*, std::vector<Rabbit*>, CompareRabbitPtrs> RabbitQueue;

int main()
{
    // seed RNG
    std::srand((unsigned)time(0));

    RabbitList rabbits;
    RabbitQueue rq;

    // load up your rabbits.
    for (int i=1;i<12;++i)
    {
        rabbits.push_back(Rabbit(std::rand() % 10 + 3,std::rand() % 20 + 5));
        rq.push(&rabbits.back());
    }

    // show rabbits
    std::copy(rabbits.begin(), rabbits.end(),
              ostream_iterator<Rabbit>(cout,"\n"));
    cout << endl;

    // remove top N rabbits, in this case 2
    for (int i=0;i<2;++i)
    {
        rabbits.remove(*rq.top());
        rq.pop();
    }

    // show rabbits again.
    std::copy(rabbits.begin(), rabbits.end(),
              ostream_iterator<Rabbit>(cout,"\n"));

    return 0;
}

Sample Run Output

[11,17]
[ 6,17]
[ 8,11]
[12,14]
[ 7, 8]
[ 6,19]
[11,16]
[10,19]
[ 6,21]
[10,14]
[ 7,13]

[11,17]
[ 8,11]
[12,14]
[ 7, 8]
[11,16]
[10,19]
[ 6,21]
[10,14]
[ 7,13]

How to avoid deleting priority_queue::top() despite a pop()?

If you are willing to take the cost of increasing the use count then as far as I can tell both boost::shared_ptr and std::shared_ptr will do:

#include <iostream>
#include <vector>
#include <memory>
#include <queue>
#include <boost/shared_ptr.hpp>

template< typename T >
struct deref_less
{
  //typedef std::shared_ptr<T> P;
  typedef boost::shared_ptr<T> P;
  bool operator()( const P& lhs, const P& rhs ) { return *lhs < *rhs; }
};

int main()
{
   //std::priority_queue< std::shared_ptr<int>, std::vector< std::shared_ptr<int> >, deref_less< int >  > pq ;
   std::priority_queue< boost::shared_ptr<int>, std::vector< boost::shared_ptr<int> >, deref_less< int >  > pq ;

    boost::shared_ptr<int>
      sp1( new int(10)),
      sp2( new int(11)),
      sp3( new int(3))
      ;

      pq.push(sp1) ;
      pq.push(sp2) ;
      pq.push(sp3) ;

      std::cout << *pq.top() << std::endl ;

      std::cout << sp2.use_count() <<std::endl ;

      //std::shared_ptr<int> sp4( pq.top() ) ;
      boost::shared_ptr<int> sp4( pq.top() ) ;

      std::cout << sp2.use_count() <<std::endl ;

      pq.pop() ;

      std::cout << sp2.use_count() <<std::endl ;
      std::cout << *sp4 << std::endl ;
}

Online std version here