If cache locality is a big concern, you should either think about implementing some variation of a B-tree, or do very fancy things like design trees with van Emde Boas layouts (which are cache oblivious and thus has excellent cache performance) [0]. Or both, at once!

Both of these things are significantly more complex than just implementing a simple max-heap, which will almost certainly perform well enough for most any practical purpose. A red-black tree will probably have significantly worse cache behaviour than a max heap, since every dereference is jumping around in memory. In a max-heap, you can count on having at least a couple of the first levels in cache when you start.

[0]: http://tildeweb.au.dk/au121/papers/soda02.pdf

Yes, if you're keeping pointers. The thing is, the gain is completely wiped out by maintaining the heap invariant which has to copy the whole thing instead of walking a single branch. The same memory bandwidth issue plagues B trees. This shows up with big trees. For small, again, you're better off with a list.

Van Emde Boas trees are better but yet more complex still. (And colored pointer variant is not available for them)

The tradeoff is speed of write vs read in case of heaps. They have pretty bad write performance.

PHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 .

I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.

RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it.

B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.

> RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage

That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.

A heap tree has a very specific structure, even if value locations have some flexibility. An RB-tree has more flexibility in its structure, with rigidity in value locations.