Problem with heaps (removal of xth elem)
Hi,
I'm trying to build some data structure I need in the future for my program.. - It ought to have very fast access for the smallest element (both removal and reading). And it has to have fast access for insertion, AND removal/updating of other elements.
It asks for using priority_queues, however they lack removal/updating of other elements than the first..
A bit more in detail:
-I get a point X, with value V, (I know already wether it would be in the list or not)
--if it's not in the list simply add it (and keep the list sorted by value V)
--if it is in the list update the list entry to the new value (and again the list should become sorted).
So especially that updating (which also could be considered "searching, removing and inserting") is the problematic point, it only has to be done a few times on average, however as the lists grows the chances become larger (so it's still not something to forget).
How would I go about this? - Could I just update the value as if it's a new entry -swapping with the parents untill it reaches a good spot- (from what I believe this ought to work, but I'm unsure how the C++ implementation would work it out).
Also:
Is there a fast way to search (possibly already in std::algorithm) the heap for the location of the point to update - given I know it's somewhere in the heap - something that uses the properties of the array being a heap?
I'm trying to build some data structure I need in the future for my program.. - It ought to have very fast access for the smallest element (both removal and reading). And it has to have fast access for insertion, AND removal/updating of other elements.
It asks for using priority_queues, however they lack removal/updating of other elements than the first..
A bit more in detail:
-I get a point X, with value V, (I know already wether it would be in the list or not)
--if it's not in the list simply add it (and keep the list sorted by value V)
--if it is in the list update the list entry to the new value (and again the list should become sorted).
So especially that updating (which also could be considered "searching, removing and inserting") is the problematic point, it only has to be done a few times on average, however as the lists grows the chances become larger (so it's still not something to forget).
How would I go about this? - Could I just update the value as if it's a new entry -swapping with the parents untill it reaches a good spot- (from what I believe this ought to work, but I'm unsure how the C++ implementation would work it out).
Also:
Is there a fast way to search (possibly already in std::algorithm) the heap for the location of the point to update - given I know it's somewhere in the heap - something that uses the properties of the array being a heap?
No need to reinvent the wheel on this one. It pretty much sounds like you're exactly describing std::set or std::map. Both are sorted lists with quick insertion and deletion of elements anywhere in the container. Searching for an existing element is quick because it's sorted, etc.
std::map has two entries per element. One is a "key" and another is a value. The map is sorted by keys, and you can use the key to look up the value. Keys and values can be any type (strings, integers, a class, whatever)
std::set is the same thing, but without a key. The set is sorted by values.
std::map has two entries per element. One is a "key" and another is a value. The map is sorted by keys, and you can use the key to look up the value. Keys and values can be any type (strings, integers, a class, whatever)
std::set is the same thing, but without a key. The set is sorted by values.
Topic archived. No new replies allowed.