> 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 c

> 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.