search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Invariant failure in extractBin #108

Closed treeowl closed 1 year ago

treeowl commented 1 year ago

extractBin doesn't distinguish between a forest that doesn't contain the minimum and a forest that is actually empty. It therefore fails to shrink the spine when it drops below a power of two. So if a queue was ever large, it will not regain the full performance of a small queue as it is drawn down. I think the easy thing is to add a constructor to MExtract to indicate that the forest is nil.

konsumlamm commented 1 year ago

I'm not sure what you mean. Isn't the shape of a binomial queue fully determined by its size? How does extractBin fail to shrink the spine?

treeowl commented 1 year ago

Yes, it's supposed to be. But our types don't inherently prevent Skip Nil, which we must avoid to maintain that uniqueness, and extractMin doesn't do what it needs to in that regard.