[DennisL123]

A winner tree uses extra space, doesn't it? That might exclude it from certain applications to be an alternative. Four-ary heaps are roughly (ymmv) twice as fast as binary heaps by exploiting cache locality in a better way for small key/value types. And it seems to be a sweet spot since eight-ary heaps don’t deliver additional improvements.

[Sesse__]

Yes, since the inner nodes duplicate information, it uses more space (roughly twice as much). I've found them generally most effective for things like merging 256 streams or doing Dijkstra with not super-many nodes (e.g. Contraction Hierarchies). If you have millions or billions of entries, then cache considerations start becoming more important than branch mispredictions and you want something like a B-heap.

[za_creature]

That's a nice niche you found (spoken from one heap fan to another) but I have to say I strongly disagree with your use of *roughly* twice as much

At best you were off by one but in the context of performance, you'd want to assign that extra to a super-root of ±inf in order to save log2n extra range checks per heap-up, no?