Hi Mark -- I held off a day in responding because I didn't have any particularly insightful information and didn't want to preclude other responses by being the first to answer. But since nobody else has picked this up yet, I'll say that I'm not aware of other implementations of a heap/priority queue in Chapel at present. I don't believe that we ever received any code contributions back from the Kassel work that you mention. If you end up with code that you're happy with and would like to contribute back to the project (as part of the standard libraries, say, or even just a test/example code), please consider it.
I think using Chapel's arrays are a reasonable way to express heaps in Chapel and, at a glance, like the approach you've taken below. I wanted to make one performance-oriented note on the use of the array's push/pop routines that you're using below (though you may already be aware of it), to note that the current default implementation of arrays doesn't amortize domain/array resizing as one would want/expect in cases like this. We have plans to provide an alternative domain map that supports amortized resizing for the next release to address this (and I'm sorry that we don't already have that ready -- I believe it's very low-hanging fruit. If it was of great short-term interest to you, we could look at whether it would be possible to bump its priority in short order). I'll note that one could also work around the lack of such a domain map by doing the recursive doubling/halving within your Heap class itself, but the amount of effort required is probably similar to (if not greater than) doing the work of the previous paragraph, so I'm not sure I'd suggest it unless you're really anxious to proceed on your own. One other note which may or may not matter for your work: At present, the push/pop-style operators are not task-safe, so if you were to parallelize operations on your heap class, you'd want to use some sort of coordination to avoid unsafe races. Hope this is helpful, and thanks for your interest in Chapel, -Brad On Tue, 28 Jul 2015, Mark Clements wrote: > Is there a standard implementation for a min-heap (or priority queue) > data structure in Chapel? (I want to implement simple discrete event > simulations in Chapel.) I noticed the interesting treatise from Kassel > by Marco Postigo Perez on "Distributed Priority Queue in Chapel" but > found no code. > > I have given a simple array-based implementation below, but I am > uncertain whether arrays are the best way to implement this. > > Kindly, Mark. > > // heap.chpl > // Mark Clements <[email protected]> 2015-07-28 > // Apache v2.0 > > class Heap { > > type eltType; > var D : domain(1) = {0..-1}; > var heap : [D] eltType; > const FIRST : int = 0; > > proc last() : int { return heap.numElements-1; } > proc left(pos : int) : int { return pos*2 + 1; } > proc right(pos : int) : int { return (pos+1)*2; } > proc parent(pos : int) : int { return (pos-1)/2; } > > proc head() : eltType { return heap.head(); } > proc clear() { heap.clear(); } > proc isEmpty() : bool { return heap.isEmpty(); } > > proc insert(x : eltType) { > heap.push_back(x); > var k = last(); > var k_parent : int; > while(k > FIRST) { > k_parent = parent(k); > if (heap[k] < heap[k_parent]) { > heap[k] <=> heap[k_parent]; > k = k_parent; > } else { > return; > } > } > } > > proc pop() : eltType { > // assert( !heap.isEmpty()) > var res : eltType = heap[FIRST]; > if (FIRST == last()) { > heap.pop_back(); > return res; > } > heap[FIRST] = heap[last()]; > heap.pop_back(); > var k = FIRST; > var k_next : int; > while(true) { > k_next = left(k); > if (k_next > last()) { > break; > } > if (right(k) <= last() && heap[right(k)] < heap[k_next]) { > k_next = right(k); > } > if (heap[k_next] < heap[k]) { > heap[k] <=> heap[k_next]; > k = k_next; > } else { > break; > } > } > return res; > } > } > > var X = new Heap(int); > X.insert(2); > X.insert(3); > X.insert(1); > for i in 1..3 do writeln(X.pop()); > > ------------------------------------------------------------------------------ > _______________________________________________ > Chapel-users mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/chapel-users > ------------------------------------------------------------------------------ _______________________________________________ Chapel-users mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/chapel-users
