Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On modern hardware the min-max heap beats a binary heap

probablydance.com

Post reply on HN
Print view View original

21–30 of 44 posts

Re: On modern hardware the min-max heap beats a binary heap

#21

Post by barbecue_sauce »

twotwotwo wrote: post #9

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 ( 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:…

I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?

Re: On modern hardware the min-max heap beats a binary heap

#22

Post by brandon_edens »

ghj wrote: post #5

In 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…

Looks like 50x to me. https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

Taking 27 milliseconds just to start the interpreter.

Re: On modern hardware the min-max heap beats a binary heap

#23

Post by dpbriggs »

barbecue_sauce wrote: post #21
twotwotwo wrote: post #9

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 ( 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:…

I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?

It's the number of children each node can have

Re: On modern hardware the min-max heap beats a binary heap

#24

Post by nwallin »

mav3rick wrote: post #15
gliese1337 wrote: post #2

I 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.

IIRC it's used in chess programs to evaluate moves.

Perhaps you're thinking of minimax? It's an unrelated concept to min-max heaps.

https://en.wikipedia.org/wiki/Minimax

https://en.wikipedia.org/wiki/Min-max_heap

Re: On modern hardware the min-max heap beats a binary heap

#25

Post by Hello71 »

mav3rick wrote: post #15
gliese1337 wrote: post #2

I 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.

IIRC it's used in chess programs to evaluate moves.

you're thinking of minimax.

Re: On modern hardware the min-max heap beats a binary heap

#26

Post by adrianmonk »

dpbriggs wrote: post #23
barbecue_sauce wrote: post #21

Earlier quoted context omitted.

I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?

It's the number of children each node can have

Maybe they're asking why the letter "d". That is, why "d-ary" instead of "n-ary" or "k-ary".

Re: On modern hardware the min-max heap beats a binary heap

#27

Post by teraflop »

barbecue_sauce wrote: post #21
twotwotwo wrote: post #9

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 ( 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:…

I don't have a formal background in CS. Any insight into why "d-" is used as the prefix?

It probably stands for "degree". In a tree, the degree of a node is how many children it has.

(And before anybody gets pedantic: technically, this is the node's "outdegree" when the tree is represented as a directed graph. If it was an undirected graph, we would have to count the parent node as well.)

Re: On modern hardware the min-max heap beats a binary heap

#29

Post by dceddia »

twotwotwo wrote: post #17
ghj wrote: post #5

In 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…

So, kind of a non sequitur, but I occasionally think about Qt's QList . When introduced, it was odd for reserving space at the beginning as well as the end, so you had constant-time inserts/removals at the beginning. That and storing pointers for any T larger than a pointer also reduced the constant factor on insertion/deletions from the middle. Since it was always stored as a list of pointer-sized items, some code c…

Along the lines of adaptive structures that change depending on how they're used, I thought this article about how JavaScript arrays work in V8 was interesting: https://ryanpeden.com/how-do-javascript-arrays-work-under-th...

V8's Array does different things depending on whether the array is sparse or packed and what data types it contains.

Re: On modern hardware the min-max heap beats a binary heap

#30

Post by nayuki »

twotwotwo wrote: post #9

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 ( 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:…

Another technique to speed up priority queues in a system with a memory hierarchy (i.e. modern computers) is the https://en.wikipedia.org/wiki/B-heap . I wonder if the author of the article is aware of this and is able to benchmark this.
Post reply on HN