c++ - Heap or Red-Black Tree? -

i willing use data structure overflow buffer of constant space. want have efficient insert importantly efficient removal of min element. thinking of using heap since have o(log(n)) find_min() , log(n) insertion , deletion. on other hand know don't understand advantage in comparison red-black tree since has o(log(n)) insert , delete , o(1) find min/max. , advantage of sorted output (i not care that).

the question related to:is red-black tree ideal data structure?

since have both of structures available std::map , boost::heap why should prefer use heap instead of red-black tree? finally, using red-black tree have o(log(n)) search time entry while heap time o(n) important since duplicates exist.

the difference in how use structures.

• binary heaps fast data structures inserting values , retrieving minimum value. however, don't support efficient searching or deletion of random values.

• red/black trees balanced binary search trees support efficient insertion, deletion, lookup of arbitrary values, , (reasonably fast) find-minimum. however, have lot of overhead compared binary heap.

if need insertion, find-minimum, , remove-minimum, binary heap superior choice because overhead lower , runtime should faster. if need insert , remove arbitrary values or lookup arbitrary values, red/black tree better choice. engineering, choosing right data structure tradeoffs.

also, note can use std::priority_queue if need binary heap; don't need use boost. it's not guaranteed std::map red/black tree; it's sort of balanced bst, balanced using other algorithm.

hope helps!