wrong term/implementation in Data.Heap.Binary and Data.Tree.Splay

[MaskRay]

I have taken a look at your project roughly and found something weird. The Data.Heap.Binary you implemented did not seem to be the Binary heap' I learned from books. Itsmerge' operation looked similar to Leftist tree and size balanced tree.

And in Data.Tree.Splay, you seemed to provide a top-down implementation of Splay trees, however, the lack of double rotates may not guarantee the O(log n) amortized time complexity.

Regards,
Ray Song

[bhickey]

It is size balanced. Insertion prefers the shallower subtree. The heap implementation you'll find in most textbooks probably involves inserting the new node at a root and bubbling it up. Since I don't have O(1) access to a leaf, I push down from the root. Barring some egregious mistake on my part, this should work.

If you want to submit a failing test, I'll be happy to patch it.

I've been thinking about reassessing the whole implementation. Enforcing elements that are instances of Ord forces the use of adapter classes in some cases. Yuck!

Brendan