search

bhickey / TreeStructures

A library of heaps and tree structures for Haskell
http://hackage.haskell.org/package/TreeStructures
BSD 3-Clause "New" or "Revised" License
11 stars 1 forks source link

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

Open MaskRay opened 12 years ago

MaskRay commented 12 years ago

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 commented 12 years ago

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