| |
| Posted by downs in reply to Leon | PermalinkReply |
|
downs
| 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());
}
}
|