<story><title>On modern hardware the min-max heap beats a binary heap</title><url>https://probablydance.com/2020/08/31/on-modern-hardware-the-min-max-heap-beats-a-binary-heap/</url></story><parent_chain></parent_chain><comment><author>noctune</author><text>And if you only need a monotone priority queue (i.e. priority queue where the popped elements are monotonically increasing&amp;#x2F;decreasing) you should consider using a radix heap. This monotone requirement can be satisfied more than you would expect when eg. using time as key or in pathfinding. I have a simple radix heap implementation here: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;mpdn&amp;#x2F;radix-heap&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;mpdn&amp;#x2F;radix-heap&lt;/a&gt;</text></comment>
<story><title>On modern hardware the min-max heap beats a binary heap</title><url>https://probablydance.com/2020/08/31/on-modern-hardware-the-min-max-heap-beats-a-binary-heap/</url></story><parent_chain></parent_chain><comment><author>twotwotwo</author><text>Like folks mentioned there, I wonder if a higher-fanout heap (people asked about 4-ary) might also do well in practice. Looking at Wikipedia (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;D-ary_heap&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;D-ary_heap&lt;/a&gt;), it looks like maybe so -- the growth in number of comparisons isn&amp;#x27;t that bad, and it mentions 4-ary heaps working well specifically.&lt;p&gt;(Like how linear search wins for small N, or insertion sort helps with small subarrays in introsort: more steps, but each step is also a lot cheaper on modern hardware due to fewer branch mispredictions, better cache locality, or something else that better fits the hardware&amp;#x27;s strengths.)</text></comment>