Wednesday, 4 August 2010
Data structures: heaps
The F#.NET Journal just published an article about data structures:
"A min-heap is a tree-based data structure that satisfies the constraint that the children at any given branch are always larger than their parent and, consequently, the minimum element is at the root. Heaps are most notable as an efficient way to implement priority queues which, in turn, underpin a variety of algorithms including some seen in previous F#.NET Journal articles. This article examines skew heaps, leftist heaps, pairing heaps and splay heaps..."
To read this article and more, subscribe to The F#.NET Journal today!
I never bought the paper from ACM, but still wonder how hard something like that is to implement?
I'd also question the value of sub-logarithmic complexities. I naturally couldn't resist the temptation to benchmark a more sophisticated heap data structure, Okasaki's bootstrapped skew binomial heap, that offered O(1) complexity for the various operations at the cost of several times more code. But the results were so poor (substantially slower than O(log n) due to a much larger prefactor) in every case that I decided not to bother presenting them here.
When you say "Melissa's algorithm" are you talking about Melissa O'Neill's genuine Sieve of Eratosthenes in Haskell? If so, I don't think you'll get close to decent performance from a purely functional style: it is just inherently very inefficient.
Subscribe to Post Comments [Atom]
Links to this post:
Subscribe to Posts [Atom]