Menu
I am willing to use a data structure as an overflow buffer of constant space. I want to have efficient insert but most importantly efficient removal of the min element. I was thinking of using a heap since I have O(log(n)) find_min() and log(n) insertion and deletion. On the other hand I know don't understand the advantage in comparison to a red-black tree since it also has O(log(n)) insert and delete but and O(1) find min/max. And the advantage of sorted output (I do not care about that).
The question is related to:Is a red-black tree my ideal data structure?
Since I have both of the structures available from std::map and from boost::heap why should I prefer to use heap instead of the red-black tree? Finally, using the red-black tree I have also O(log(n)) search time for an entry while for a heap the time is O(n) which is important since duplicates exist.
669
Red-black tree: total ordering: left child < parent < right child. Heap: dominance: parent < children only. Red-black tree: pointers used to represent structure of tree, so overhead per element. Typically uses a number of nodes allocated on free store (e.g. using new in C++), nodes point to other nodes.
Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete.
The fundamental distinction is that whereas the Binary Search Tree does not allow duplicates, the Heap allows. The BST is ordered, while Heap is not. So, if order is important, BST is the way to go.
AVL trees provide faster lookups than Red-Black Trees because they are more strictly balanced. In this, the color of the node is either Red or Black.
The difference is primarily in how you would use the structures.
Binary heaps are very fast data structures for inserting values and retrieving the minimum value. However, they don't support efficient searching or deletion of random values.
Red/black trees are balanced binary search trees that support efficient insertion, deletion, lookup of arbitrary values, and (reasonably fast) find-minimum. However, they have a lot of overhead compared to a binary heap.
If all you need is insertion, find-minimum, and remove-minimum, the binary heap is probably a superior choice because the overhead is lower and the runtime should be faster. If you need to insert and remove arbitrary values or lookup arbitrary values, the red/black tree is probably the better choice. As with all engineering, choosing the right data structure is all about tradeoffs.
Also, note that you can use std::priority_queue if you need a binary heap; you don't need to use Boost. It's also not guaranteed that std::map is a red/black tree; it's probably some sort of balanced BST, but it could be balanced using some other algorithm.
Hope this helps!
200
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
