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.
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!