The fastest way of doing a heap I've found is generally: Don't. For many of the relevant operations (graph search, merging streams, etc.), you can do just as well with a winner-tree; it can usually be updated branch-free with min/max operations, whereas with a heap you'll usually have completely unpredictable branches for every single operation.

A winner-tree, or its counterpart the loser-tree (for min instead of max), is a very simple binary tree: Bottom layer is all your values (2^N of them). The layer above that is the highest of pairs of values. The layer above that is the highest of pairs of pairs. And so on, until you get to the top of the tree, which contains the largest value. Updating a value is trivial; you overwrite the relevant one at the bottom, and then run exactly log2(n) max operations upwards until the you hit the root. Inserting and deleting may, of course, be more complicated.

▲

DennisL123 6 days ago | parent | next [-]

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__ 6 days ago | parent [-]

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 6 days ago | parent [-]

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?

▲

Sesse__ 6 days ago | parent [-]

I don't think I understand what you are saying. Anyway, if you are strapped for space, do not use a winner tree.

	▲	za_creature 5 days ago \| parent [-]
		Ah, I meant that for a classic heap, it's convenient to assign h[0] to the limit of your goal function (e.g. -inf for a min heap) cause that way you can skip the while i>0 check and just do while h[i>>1] > min(h[i], h[i+1]), asserting that the condition is definitely false when i < 2 I guess that it's not as important when you're explicitly willing to pay the piper and run the full log2n iterations just for the sake of branch predictability. Thanks for the algo though, before today I never would've thought about doing a branchless downheap with i = i<<1 + h[i<<1] != h[i]

▲

RossBencina 5 days ago | parent | prev [-]

For running min/max there is an efficient O(1) algorithm by none other than Daniel Lemire: https://lemire.me/en/publication/arxiv0610046/