You can also change the memory layout to that of a binary heap, instead of the usual sorted order. That puts the next index at either (2i + 1) or (2i + 2). With

You can also change the memory layout to that of a binary heap, instead of the usual sorted order. That puts the next index at either (2i + 1) or (2i + 2). With proper alignment, those will be in the same cache line up to 4 iterations in the future, regardless of which way you descend the tree. So you can do a branchless prefetch version with much better than a 50% prefetch accuracy. This only helps once you're hitting L3 cache, though. See https://news.ycombinator.com/item?id=10410676 https://news.ycombinator.com/item?id=10410676 for previous discussion.