mlimber wrote:
On Aug 5, 2:25 pm, Stuart Golodetz
<sgolod...@NdOiSaPlA.pMiPpLeExA.ScEomwrote:
>Stuart Golodetz wrote:
>>Just wondering what you'd recommend in terms of a C++ priority queue
implementation that supports bubble-up and bubble-down operations
please? std::priority_queue doesn't seem to support doing that, and I
couldn't find an alternative in Boost. I could write my own, but that
feels a little bit like reinventing the wheel, so I thought it was worth
asking first.
When I said "bubble-up" and "bubble-down", what I really meant was
increase key and decrease key (not necessarily respectively). Just to
clarify :-)
Technically a PQ doesn't support bubble/key operations. You're wanting
a heap. Check out std::make_heap, std::sort_heap, and related
functions.
Cheers! --M
Thanks, think I may have been confusing the interface and the
implementation (since PQs are often implemented as heaps internally).
That being said, it is looking increasingly as if I'll have to cook my
own at least to some extent: I need dictionary lookup for the decrease
key/increase key operations, I don't think I can just use the simple
approach which is possible when you already have a pointer to the
element whose key you're trying to change. But I'll take a look at the
heap operations and see if I can make use of them somehow to avoid
completely reinventing things...
Cheers for the help :-)
Stu
