Re: What's the difference between the priority queue & set & heap ?
on Fri Aug 10 2007, Le Chaud Lapin <jaibuduvin-AT-gmail.com> wrote:
On Aug 8, 10:20 pm, PicO <bekerp...@gmail.com> wrote:
i need some explanation about the difference between priority queue &
set & heap ... as they all sort the data in ( n log n ) ... but the
only i see that priority queue only can pop the top ( maximum
element ) while set and heap can erase any element ...
i also read that .. i can make a heap from priority queue ....
how ? ...
I think you mean it the other way around. Most computer science books
on data structures show how to make a priority queue from a heap,
typically starting with binary heaps and moving to progressively more
complex heaps (Fibonacci, etc.)
A word of caution:
In my (limited) experience in data structures, I have found few other
places where extreme discipline is required in thinking about exactly
what is the thing you are trying to make than with priority queues. To
give you an example, some computer science books claim that you can
implement Dijkstra's algorithm "using priority queues." Also, the C++
standard prescribes a "priority queue". But if you try to implement
Dijkstra's algorithm with template priority_queue<> from STL, you will
enter a state of prolonged misery until you finally conclude that
Dijkstra's algorithm can *not* be implemented with a priority queue.
That said, technically, for optimal
performance Dijkstra needs a mutable priority queue with an update
operation, as in
http://svn.boost.org/trac/boost/browser/trunk/boost/pending/mutable_queue.hpp
It's hard to see at first, but that update operation doesn't make any
difference to the big-O speed. However it does change the worst-case space
requirements:
http://lists.boost.org/Archives/boost/2002/01/23978.php
Unfortunately, the need for update considerably complicates the
algorithm (http://tinyurl.com/36jmso).
Moral: if you know your graph is not densely-connected (i.e. |E| is
close to |V|), you can get away with a much simpler version of
Dijkstra that uses a plain priority queue. However, that sort of
optimization should probably be a last resort.
Real Moral: Bite the bullet and use the Boost.Graph implementation of
Dijkstra; it will save you lots of pain in the long run ;-)
You will then be left asking, "If not, then what can it be
implemented with?" You will discover that the thing is
not-yet-named, but has a structure that deceptively similar to a
priority queue, but is not a priority queue.
It's known to some as MutableQueue ;-)
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
The Astoria Seminar ==> http://www.astoriaseminar.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]