On modern hardware the min-max heap beats a binary heap
probablydance.com
On modern hardware the min-max heap beats a binary heap
1–10 of 44 posts
Re: On modern hardware the min-max heap beats a binary heap
#2I have used a min-max heap once. I don't remember why I needed it at the time--it was a previous job--but I do remember that I had to roll my own, because it's just not that popular of a data structure, and it was the obvious and only good solution to the problem at the time.
So, it's nice to see a detailed analysis of the structure like this! Perhaps if it becomes more popular, I will find more places to use it.
Re: On modern hardware the min-max heap beats a binary heap
#3If you need a min-max heap (or double ended heap) in Go here is one I've used: https://github.com/aalpar/deheap
Very useful when you need it!
Re: On modern hardware the min-max heap beats a binary heap
#4Impressive. Looking forward to the d-heap article.
Re: On modern hardware the min-max heap beats a binary heap
#5In certain domains, the trend has been to give up constant factors in order to increase programmer productivity (e.g., python pays a 10x slowdown but is batteries included).
So in that case I would use this data structure even if it weren't faster. I can't count the number of times I have had to mess with inserting negative priorities into a min heap to create a max heap! We should just have one data structure that does both.
(though taking this idea to the logical extreme means we should just use Order Statistic Tree for everything since it not only gives you log(n) min/max, but also log(n) find kth and get rank of x)
Re: On modern hardware the min-max heap beats a binary heap
#6In certain domains, the trend has been to give up constant factors in order to increase programmer productivity (e.g., python pays a 10x slowdown but is batteries included). So in that case I would use this data structure even if it weren't faster. I can't count the number of times I have had to mess with inserting negative priorities into a min heap to create a max heap! We should just have one data structure that d…
Surely you should ve able to just use a different comparator instead (> instead of <).
Re: On modern hardware the min-max heap beats a binary heap
#7Impressive. Looking forward to the d-heap article.
Yeah I was going to say, it sounds like it is faster because it has higher arity rather than because it is min and max. So if you only need min or max a d-heap is probably better. Hopefully he will update the article.
https://en.wikipedia.org/wiki/D-ary_heap
(Also I didn't know they were called d-heaps, thanks!)
Re: On modern hardware the min-max heap beats a binary heap
#8It would be neat to fire this up on an older processor which doesn’t have modern instruction-level parallelism and verify the difference in performance
Re: On modern hardware the min-max heap beats a binary heap
#9Like folks mentioned there, I wonder if a higher-fanout heap (people asked about 4-ary) might also do well in practice. Looking at Wikipedia (https://en.wikipedia.org/wiki/D-ary_heap), it looks like maybe so -- the growth in number of comparisons isn't that bad, and it mentions 4-ary heaps working well specifically.
(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's strengths.)
Re: On modern hardware the min-max heap beats a binary heap
#10In certain domains, the trend has been to give up constant factors in order to increase programmer productivity (e.g., python pays a 10x slowdown but is batteries included). So in that case I would use this data structure even if it weren't faster. I can't count the number of times I have had to mess with inserting negative priorities into a min heap to create a max heap! We should just have one data structure that d…
Surely you should ve able to just use a different comparator instead (> instead of <).
Not in python! But I guess using negatives is the same as using different key (which is what python uses instead of comparators).
The real problem is if you need min/max at the same time. Then you not only need a min heap and max heap, you also need to track what was already popped from either heap! This is because in python you can't delete an element if it's not at the root. So tracking "tombstones" will let you pop from one heap, then know to ignore it the next time it comes up in the other heap.
This is of course super complicated to maintain and I get it wrong all the time. Luckily only shows up in algo interview problems.