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.

3
Contributors
5
Replies
6
Views
9 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:
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.

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.

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

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