www.digitalmars.com         C & C++   DMDScript  

D - BinaryHeap for A*

reply Leon <vdvleon gmail.com> writes:
Hello,

I am getting started with D now. I want to implement the A* algorithm, but
then i need a BinaryHeap. Then i found that i can find that in
std.algorithm.BinaryHeap, but then i noticed that you only can make a heap of
an already existing range (array). What i want is a dynamic heap.

So:

BinaryHeap heap; // of int's
heap.add(43);
heap.add(333);
heap.pop() // => 333 (largest value in the heap)

It this posible? (in a fast way?)

Thank you
Jul 26 2009
next sibling parent downs <default_357-line yahoo.de> writes:
Leon wrote:

 Hello,
 
 I am getting started with D now. I want to implement the A* algorithm, but
 then i need a BinaryHeap. Then i found that i can find that in
 std.algorithm.BinaryHeap, but then i noticed that you only can make a heap of
 an already existing range (array). What i want is a dynamic heap.
 
 So:
 
 BinaryHeap heap; // of int's
 heap.add(43);
 heap.add(333);
 heap.pop() // => 333 (largest value in the heap)
 
 It this posible? (in a fast way?)
 
 Thank you


This NG is not used anymore. Please direct all further posts to digitalmars.D
or digitalmars.D.learn. :)

That being said, here's a simple binary heap.

module binheap;

typedef void RuntimePred;

/// Pred(field, parent): does predicate hold for those two?
struct BinHeap(T, alias Pred = RuntimePred) {
  T[] field;
  static if (is(Pred == RuntimePred)) bool delegate(T, T) pred;
  else bool pred(T a, T b) { return Pred(a, b); }

  size_t getParent(size_t i) {
    return ((i + 1) >> 1) - 1; // sketch it on a piece of paper to see what I
mean
  }
  size_t getChild(size_t i) {
    return ((i + 1) << 1) - 1;
  }
  private void swap(size_t a, size_t b) {
    auto temp = field[a];
    field[a] = field[b];
    field[b] = temp;
  }
  // See Wikipedia for algorithms
  void push(T t) {
    field ~= t;
    auto id = field.length - 1;
    while (id) { // percolate-up
      auto parent = getParent(id);
      if (!pred(field[id], field[parent])) swap(id, parent);
      else break;
      id = parent;
    }
  }
  T pop() {
    auto res = field[0];
    field[0] = field[$-1];
    field = field[0 .. $-1];
    size_t id;
    while (true) { // percolate-down
      auto child1 = getChild(id), child2 = child1 + 1;
      if (child1 >= field.length) break; // bottom
      if (child2 >= field.length) { // only one possibility
        if (!pred(field[child1], field[id])) swap(id, child1);
        break; // necessarily also done
      }
      auto new_id = child1;
      if (pred(field[child1], field[child2])) // in a max-heap, if (b > a)
        new_id = child2;

      if (!pred(field[new_id], field[id])) swap(new_id, id);
      else break;

      id = new_id;
    }
    return res;
  }
  T top() {
    return field[0];
  }
}

bool greater(T)(T a, T b) { return b > a; }

import std.random, std.stdio;
void main() {
  BinHeap!(int, greater) bh;
  for (int i = 0; i < 20; ++i)
    bh.push(rand() % 100);
  writefln(bh.field); // flattened bintree representation
  for (int i = 0; i < 20; ++i) {
    writefln(bh.pop());
  }
}
Jul 27 2009
prev sibling parent Benjamin Shropshire <ao pathlink.com> writes:
Reply to Leon,


 Hello,
 
 I am getting started with D now. I want to implement the A* algorithm,
 but then i need a BinaryHeap. Then i found that i can find that in
 std.algorithm.BinaryHeap, but then i noticed that you only can make a
 heap of an already existing range (array). What i want is a dynamic
 heap.
 
 So:
 
 BinaryHeap heap; // of int's
 heap.add(43);
 heap.add(333);
 heap.pop() // => 333 (largest value in the heap)
 It this posible? (in a fast way?)
 
 Thank you
 


IIRC the Tango Heap fits the bill and you can extract it to be used on it's 
own without much work.

http://www.dsource.org/projects/tango/browser/trunk/tango/util/container/more/Heap.d
Jul 29 2009