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.

Pony

Consider a ring buffer. Don't know if it's appropriate for your uses. – Traveled

possible duplicate of Heap vs Binary Search Tree (BST) – Giustino

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!

Hoodoo

Thank you for your quick answer. In my data I have duplicates so I cant avoid find() which is expensive on a heap. On the other hand insert and erase are faster in a heap but logarithmic in the red-black tree. I guess the red-black tree is the right answer for this one.However, I have seen in a paper using a heap even if they have find() operations and thats why I am confused. – Pony

A heap is not a search data structure; you can, however, store the position of an element inside the heap, so at a later time you can change its priority (which will move the element up or down accordingly). Many sweep-line-based geometric algorithms require this kind of "find-and-update". – Tengler

To add to what DanielKO said, I once saw a custom binary heap that maintained each item's index within the items themselves. The creator was only interested in O(1) contains, which that enabled (items[item.index] == item), but you could also use it to greatly speed up other operations. – Plastometer

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.

Farinose