The clear difference is that a red-black tree can support O(logn) removal, compared to heap's O(n) removal.
However, it looks like all operations for a red-black tree are faster/equal tothose of a heap. So my question is, why do we ever use a heap over red-black tree? It seems to me a red-black tree can do anything a heap can do, but faster/equal.
Thanks.
A principal use case for a minheap is a priority queue where the main operations as push(newval), pop_smallest(), inspect_smallest().
In this situation a heap wins because the inspect_smallest() search step is O(1). The smallest value is always at position zero.
Also, while both Red Black Trees and Minheaps have O(log n) insertion and removal times, the constant factor is smaller for minheaps.
Also, heaps can be represented much more compactly than for a red-black tree. There is no need for a "coloring" bit and the tree itself is easily represented as an array, so there is no need to store pointers.
In short, if an application doesn't need general search and can instead focus on the lowest value, then a heap provides a simpler and cheaper alternative.