Priority_Queue

[hgedek]

Hi.I need an answer to my heap problem.
I am creating a 1000 items priority_queue (priority_queue,SortClass>);

Sometimes I need deleteThis(Molecule *mol) function.So this function can delete any item at any index.Pop wont work here if I dont use pop-push until the target.But this takes long time.So I want to learn that.I got the priority_queue codes.So I can use vector which is holding my items.Using a linear search and delete I can remove item from vector but heap is giving error.After deleteting I cant push or pop.Invalid heap....So what is problem I am doing?Thanks.

[bugmenot]

You can't really delete an arbitrary item from a priority queue easily; only the item with the highest priority. Maybe you should read up on what priority queues are:
http://en.wikipedia.org/wiki/Priority_queue

The items in the priority queue (implemented as a binary heap) have some structure, but are not in sorted order; so your method will not work.

Perhaps you should be using sets instead. They can remove items easily.

[hgedek]

Hi.I looked for set.But I couldnt find that info:Is set like to priority_queue according to algorithm?I need a heap algorithm.Because of this I used PQueue.Thanks.

[bugmenot]

what problem are you trying to solve? and why do you need to remove elements?

[hgedek]

I am creating a >1000 items heap.You know removing the first is so easy.But removing the 700 etc. item is diffucult.Because priority_queue hasnt a remove function.Now I learnt set has erase and find.So this can help.But I want to learn that:Can I use set instead of priority_queue or heap.Thanks.

[vijayan121]

> Is set like to priority_queue according to algorithm?I need a heap algorithm.
no.

> removing the first is so easy.
> removing ...is difficult. Because priority_queue hasnt a remove function.
the simplest solution may be to write your own priority_queue which has an erase function. (it will not be a priority_queue in a strict sense, but a heap with erase functionality).

#include <vector>
#include <algorithm>
#include <iterator>

template< typename T, typename sequence_type = std::vector<T>,
          typename cmp_function_t  =
               std::less< typename sequence_type::value_type > >
struct my_priority_queue
{
  // *** note: ignoring c++0x concepts requirements ***
    // 1. T has AssignableConcept
    // 2. sequence_type has SequenceConcept
    // 3. sequence_type has RandomAccessContainerConcept
    // 4. T and sequence_type::value_type have SameTypeConcept
    // 5. cmp_function_t has bool(T,T) BinaryFunctionConcept

  typedef typename sequence_type::value_type value_type;
  typedef typename sequence_type::reference reference;
  typedef typename sequence_type::const_reference const_reference;
  typedef typename sequence_type::size_type size_type;
  typedef sequence_type container_type;

  explicit my_priority_queue(
        const cmp_function_t& fn = cmp_function_t(),
        const sequence_type& cntr = sequence_type() )
    : c( cntr ), comp( fn )
    { std::make_heap( c.begin(), c.end(), comp ) ; }

  template<typename iterator_t>
      my_priority_queue( iterator_t begin, iterator_t end,
         const cmp_function_t& fn = cmp_function_t(),
         const sequence_type& cntr = sequence_type() )
    : c( cntr ), comp( fn )
    {
       c.insert( c.end(), begin, end ) ;
       std::make_heap( c.begin(), c.end(), comp ) ;
    }

  bool empty() const { return c.empty() ; }

  size_type size() const { return c.size() ; }

  const_reference top() const { return c.front(); }

  void push( const value_type& v )
  {
    c.push_back(v);
    std::push_heap( c.begin(), c.end(), comp ) ;
  }

  void pop()
  {
    std::pop_heap( c.begin(), c.end(), comp ) ;
    c.pop_back();
  }

  void erase( const value_type& v )
  {
    typedef typename sequence_type::iterator iterator ;
    iterator where = std::find( c.begin(), c.end(), v ) ;
    if( where != c.end() )
    {
      c.erase( where ) ;
      std::make_heap( c.begin(), c.end(), comp ) ;
    }
  }

  protected:
    sequence_type c ;
    cmp_function_t comp ;
} ;