Re: What's the difference between the priority queue & set & heap ?
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.
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.
Tread with caution, and be prepared name your "things".
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]