Heap or Red-Black Tree?

Question

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.

Answer 1

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!

Answer 2

A heap is easily implemented in contiguous memory, i.e. an array. A red-black tree is typically constructed with a separate heap allocation for each node. The red-black tree ends up accessing memory all over the heap for each tree traversal. This is worst-case cache behavior. Even though the algorithmic complexity of certain operations is the same for both structures, the constant overhead for the red-black tree is much higher.