Searchable structure
The problem is accessing a range of values in two different ways. First, by priority; which is implemented quite simply with a bunch. In addition, it should be possible to "mark" each value with one or more characters through which the list of items can be accessed.
This would be easy enough to implement efficiently by referencing the same data in two different structures. However, they must create a cohesive queue. Therefore, items removed from one structure must also be removed from another, an operation for which the heap is not very suitable.
Is there a data structure that is capable of providing efficient ordering on a single value (ideally optimized for push / popping) without completely degrading the performance of finding / removing nodes in arbitrary locations?
source to share
You can remove any item from the binary heap in O (log (n)) as long as you know which one to remove. Any node can be thought of as a valid heap, and you can use the delete-max (or delete-min) operation in the same way as in general.
The only problem is how do you know which one to remove? I think I have a solution for this. Use a wrapper for the saved class that references the heap node and removes that node from the wrapper destructor. When you want to remove any item from the collection, you can simply remove the wrapper using any of the indices and it will take care of the rest. When you insert something into a collection, you need to create a wrapper object and pass a reference to the heap node.
Here is the C ++ code:
template <class T> class Wrapper {
T data;
HeapNode* index_heap;
Foo* index_tags;
Bar* index_queue;
public: ~Wrapper() {
index_heap->delete_max();
index_tags->delete_foo();
index_queue->delete_bar();
}
};
source to share