Re: Sequence container with fast random access and fast insertion/removal (wherever)
Martin Knoblauch Revuelta wrote:
Le Chaud Lapin wrote:
[..] If you look at the binary heap
algorithm, it doesn't say anything about whether you are trying to
insert a node that is already present. And in general, if you *are*
trying to insert a duplicate node, chances are the one that is already
present is in some weird place in the tree, and you never see it during
re-insertion.
You can always keep a pointer to the heap element. This way you can
extract it before reinsertion. The heap interface should return some
kind of reference to the element after insertion. This would require
the heap to be implemented in a tree, instead of the usual array
implementation.
Yes, then it is no longer a heap, but a set, perhaps using an AVL tree,
that allows fast [O(logn)] determination of the node with lowest (or
highest value). That's what I ended up doing in my implementation of
two classes:
1. Prioritized_Set<Element, Priority>
2. Prioritized_Associative_Set<Left, Right, Priority>
After doing a tour of various heap implementations, I settled on an
old-fashioned set.
If I were you, I would extract the essential two functions from your
AVL array and make them global template functions that operate on
binary-tree-like structures. That way, when it comes time to implement
a new structure, you can reuse your functions. This is what I did, and
it feels great.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]