complexity error in the pairing heap API

fsprojects / FSharpx.Collections

FSharpx.Collections is a collection of datastructures for use with F# and C#.

http://fsprojects.github.io/FSharpx.Collections/

Apache License 2.0

247 stars 78 forks source link

complexity error in the pairing heap API #70

Closed nestordemeure closed 6 years ago

nestordemeure commented 7 years ago

Some (merge and insert) of the given complexities for the pairing heap implementation seem to be wrong (it might be a copy-pasting error). They are not coherent with Chris Okasaki's Functional Data Structures (p25), neither wikipedia (which has a source for the complexity of the delemin operation).

The correct values should be :

insert : O(1) worst case
merge : O(1) worst case
tryMerge : O(1) worst case

jackfoxy commented 6 years ago

@nestordemeure I Okasaki's Purely Functional Data structures:

Many imperative implementations support insert, merge ... in O(1)amortized time ... unfortunately, the bounds for pairing heaps have only been conjectured, not proved.

In the paper you cite he also hedges, a little. I couldn't find a publication data in that paper, btw.

The correct O(1) is amortized, not worst case.

I would accept a PR with this change, if you are interested in doing it.

nestordemeure commented 6 years ago

It is O(1) amortized indeed. I just submitted a pull request with the corresponding modifications.

jackfoxy commented 6 years ago

https://github.com/fsprojects/FSharpx.Collections/pull/93