Efficient heap data structure

[Mark Clements]

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 <firstname.lastn...@ki.se> 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
Chapel-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/chapel-users