## D - BinaryHeap for A*

• Leon (12/12) Jul 26 2009 Hello,
• downs (68/85) Jul 27 2009 This NG is not used anymore. Please direct all further posts to digitalm...
• Benjamin Shropshire (4/22) Jul 29 2009 IIRC the Tango Heap fits the bill and you can extract it to be used on i...
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.pop() // => 333 (largest value in the heap)

It this posible? (in a fast way?)

Thank you
```
Jul 26 2009
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.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
```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.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