Talk:Pairing heap

I think some explanations need refinement

1. Isn't the definition supposed to be: empty heap | root + list of non empty pairing-heaps?

   Not specifying that the sub-heaps in the children-list cannot be empty-heap is kinda misleading.

2. seems that merge is a symmetric operation, but not associative. so if we merge a list of sub-heaps in groups of 3 (or more), and then merge the resulting list - it would matter which direction we did each part. but merging in pairs is symmetric, so what does it matter in merge-pairs() whether we go left-to-right or otherwise on each level?

--Itaj Sherman (talk) 01:49, 11 October 2013 (UTC)

Open Question is Already Solved

The article states that:

"Moreover, it is an open question whether a o(log n) amortized time bound for decrease-key and a O(1) amortized time bound for insert can be achieved simultaneously.[8]"

This question appears to be solved. For example, Amr Elmasry in his TALG'17 paper "Toward Optimal Self-Adjusting Heaps" gives a data structure with O(1) insert and O(log log n) decrease-key.

--2001:62A:4:413:5D51:AF10:173B:A57C (talk) 12:41, 15 November 2018 (UTC)

Thanks; the article has been updated. 167.88.12.231 (talk) 05:09, 2 July 2019 (UTC)

The "Often faster than array-based heaps" claim

In the text it is currently stated "that pairing heaps are often faster in practice than array-based binary heaps and d-ary heaps". When I read this yesterday I found this to be quite a strong and surprising claim so I checked the 3 cited sources. My conclusions was that the claim seems not justified and I removed it. Unfortunately this change was reverted.

Here I want to describe again in more detail why I believe that the current claim is unsourced.

Lets me focus on the most recent paper by Larkin, Sen, and Tarjan (2014) first because it seems to be of excellent quality, up to date and most relevant.

If you read that paper you see that the pairing heap wins only 9 out of 41 of the performed benchmarks while the implicit d-ary heaps wins 17 out of 41. At the end of the paper they just conclude that different data structures are favorable in different situations. Our strong statement certainly cannot be justified based on that.

The reverter of my change suggested the wording "sometimes" instead of "often" as a compromise. I see one more reason though why we should just remove the claim entirely: What does "array-based" mean exactly and is the implementation of the implicit heaps in the sources of that form?

In the last paper I think not because it actually uses pointers to individally managed memory nodes. This is done to keep track of nodes in the data structure and to support the "decrease-key" operation on them at a later point. However this obviously negates some of the cache related benefits and I argue that this is not truely "array-based" anymore. We don't define what this means in the Wikipedia article but I am pretty sure most people imagine an entirely implicit data structure without auxillary data and pointers. The linked source also benchmarks "truely" implicit array-based d-ary heaps (which they called "implicit_simple_n") but they can only participate in some benchmarks in which pointer stability is not needed. However in ALL 9 benchmarks this variant paricipated it was also the fastest and in particular faster than pairing heaps. Sometimes significantly so like in the heap sorting benchmark.

I also checked out the two other linked sources. The second one by Moret and Shapiro does indeed state that pairing heaps were faster than binary heaps for them. However this was 30 years ago when the computing landscape was quite different and we do not know to which extent their implementation was "array-based". In contrast to the newer paper they did not publish source codes or timings.

Therefore I propose to remove the "pairing heaps are often faster in practice than array-based binary heaps and d-ary heaps" statement again entirely.

2A02:810D:4BC0:33B8:64EA:C348:8F07:DFBB (talk) 22:53, 2 September 2020 (UTC)

I don't agree with removing the statement entirely. The paper by Moret and Shapiro is somewhat old, but is not contradicted by more recent works I'm aware of. Larkin found mixed results, and we should say that; they also found that the best results came from dropping the node-tracking functionality needed for things like decrease-key, and we should definitely say that, because dropping that functionality is incompatible with a lot of the 'normal' things one would use a heap for, like Dijkstra's algorithm. It's clear that if you're doing a bunch of inserts and delete-mins, an "implicit simple" binary heap will beat all contenders. But in circumstances where you need to decrease or delete nodes, the latter two papers both report that pairing heaps often won out. Sneftel (talk) 11:47, 3 September 2020 (UTC)