Hi.I need an answer to my heap problem.
I am creating a 1000 items priority_queue (priority_queue<Molecule*,vector<Molecule*>,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.

8 Years
Discussion Span
Last Post by vijayan121

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:

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.


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.


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.


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

> 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 )
    std::push_heap( c.begin(), c.end(), comp ) ;

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

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

    sequence_type c ;
    cmp_function_t comp ;
} ;
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.