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