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!
Labels: data structure, heap, priority queue
Comments:
Links to this post:
<< Home
The Fusion tree algorithm by Fredman and Willard implements the minimum operation in O(1) time and insert and extract-min operations in time.
I never bought the paper from ACM, but still wonder how hard something like that is to implement?
I never bought the paper from ACM, but still wonder how hard something like that is to implement?
Also, maybe one could use such a structure behind Melissa's algorithm and hope to have it perform to a speed closer to your superfast implementation?
@David: As I understand it, Fusion trees are for small integers only.
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.
Post a Comment
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:
<< Home
Subscribe to Posts [Atom]