www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Min-Heap and Hash Table help

reply "Chris Pons" <cmpons gmail.com> writes:
I'm trying to work with and implement and priority queue( 
min-heap ) and a hash table. This is the first time I've worked 
with these data structures so I looked up some information about 
them to gain an understanding.

 From what I read, a min-heap is a binary tree that is sorted by a 
priority. In my case I have a struct called Node for an A* 
algorithm that I wanted to place in a min-heap sorted by an 
integer, their f score. Initially the min-heap will only have one 
item in it with others added later.

 From looking at the Library reference I have gathered this:

struct Node
{
	bool walkable;		//Whether this node is blocked or open
	vect2 position;		//The tile's position on the map in pixels
	int	xIndex, yIndex; //The index values of the tile in the array
	Node*[4] connections; //An array of pointers to nodes this 
current node connects to
	Node* parent;
	int gScore;
	int hScore;
	int fScore;
}

Class AStar
{
Node[] a;
Node start;

void FindPath(Node[] PathGraph )
{
a ~= start;
//Heapify as min-heap by f Score?
openList = heapify(a, "a.fScore > b.fScore" );

//...After some work If I want to add a new Node

Node new;
//Will the list stay sorted??
openList.insert( new );
}
}

How would I create a min-heap sorted by fScore?
Will the list stay sorted after I add a new node?

As far as hash tables goes, it seems like I need to use an 
associative array, is that right?

What exactly would the key/hash be? How would I implement this if 
the hash table is supposed to contain the struct Node?
Apr 02 2012
parent reply Justin Whear <justin economicmodeling.com> writes:
On Tue, 03 Apr 2012 00:47:56 +0200, Chris Pons wrote:


 I'm trying to work with and implement and priority queue( min-heap ) and
 a hash table. This is the first time I've worked with these data
 structures so I looked up some information about them to gain an
 understanding.
 
  From what I read, a min-heap is a binary tree that is sorted by a
 priority. In my case I have a struct called Node for an A* algorithm
 that I wanted to place in a min-heap sorted by an integer, their f
 score. Initially the min-heap will only have one item in it with others
 added later.
 
 How would I create a min-heap sorted by fScore? Will the list stay
 sorted after I add a new node?
 
 As far as hash tables goes, it seems like I need to use an associative
 array, is that right?
 
 What exactly would the key/hash be? How would I implement this if the
 hash table is supposed to contain the struct Node?


BinaryHeap in std.container can be made to work as a min-heap, in fact 
the documentation specifically mentions such a use: http://dlang.org/
phobos/std_container.html#BinaryHeap
Apr 02 2012
parent reply "Chris Pons" <cmpons gmail.com> writes:
Yes, I did see that. How would I set the predicate to sort by 
fScore? An integer in my struct.

On Monday, 2 April 2012 at 22:53:55 UTC, Justin Whear wrote:

 On Tue, 03 Apr 2012 00:47:56 +0200, Chris Pons wrote:


 I'm trying to work with and implement and priority queue( 
 min-heap ) and
 a hash table. This is the first time I've worked with these 
 data
 structures so I looked up some information about them to gain 
 an
 understanding.
 
  From what I read, a min-heap is a binary tree that is sorted 
 by a
 priority. In my case I have a struct called Node for an A* 
 algorithm
 that I wanted to place in a min-heap sorted by an integer, 
 their f
 score. Initially the min-heap will only have one item in it 
 with others
 added later.
 
 How would I create a min-heap sorted by fScore? Will the list 
 stay
 sorted after I add a new node?
 
 As far as hash tables goes, it seems like I need to use an 
 associative
 array, is that right?
 
 What exactly would the key/hash be? How would I implement this 
 if the
 hash table is supposed to contain the struct Node?


 BinaryHeap in std.container can be made to work as a min-heap, 
 in fact
 the documentation specifically mentions such a use: 
 http://dlang.org/
 phobos/std_container.html#BinaryHeap
Apr 02 2012
parent reply Justin Whear <justin economicmodeling.com> writes:
On Tue, 03 Apr 2012 01:06:54 +0200, Chris Pons wrote:


 Yes, I did see that. How would I set the predicate to sort by fScore? An
 integer in my struct.
 


auto myHeap = BinaryHeap!`a.fScore > b.fScore`( rangeOfNodes );
Apr 02 2012
parent reply "Chris Pons" <cmpons gmail.com> writes:
On Monday, 2 April 2012 at 23:30:38 UTC, Justin Whear wrote:

 On Tue, 03 Apr 2012 01:06:54 +0200, Chris Pons wrote:


 Yes, I did see that. How would I set the predicate to sort by 
 fScore? An
 integer in my struct.
 


 auto myHeap = BinaryHeap!`a.fScore > b.fScore`( rangeOfNodes );


Ok, makes sense, will the heap be automatically sorted every time 
I add a new item ? Might be a dumb question, but i'm going to be 
removing and adding many nodes.
Apr 02 2012
parent reply "Henry Robbins Gouk" <henry.gouk gmail.com> writes:
On Monday, 2 April 2012 at 23:42:45 UTC, Chris Pons wrote:

 On Monday, 2 April 2012 at 23:30:38 UTC, Justin Whear wrote:

 On Tue, 03 Apr 2012 01:06:54 +0200, Chris Pons wrote:


 Yes, I did see that. How would I set the predicate to sort by 
 fScore? An
 integer in my struct.
 


 auto myHeap = BinaryHeap!`a.fScore > b.fScore`( rangeOfNodes );


 Ok, makes sense, will the heap be automatically sorted every 
 time I add a new item ? Might be a dumb question, but i'm going 
 to be removing and adding many nodes.


I haven't looked at the heap docs for Phobos, but the whole point
of a heap is that when you add/remove elements it remains in heap
order. In the case of a min-heap: the smallest node is at the
root and each child node is another heap in heap order.
Apr 02 2012
parent reply "Henry Robbins Gouk" <henry.gouk gmail.com> writes:
 each child node is another heap in heap order.


That should be: each child node is the root node of another heap 
in heap order.
Apr 02 2012
parent reply "Chris Pons" <cmpons gmail.com> writes:
I'm still having troubles with the min-heap.

Node[] a;
auto b = BinaryHeap!"a.fScore > b.fScore"( a[] );


Error	1	Error: template instance BinaryHeap!("a.fScore >
b.fScore") BinaryHeap!("a.fScore > b.fScore") does not match
template declaration BinaryHeap(Store,alias less = "a < b") if
(isRandomAccessRange!(Store) ||
isRandomAccessRange!(typeof(Store.init[])))	C:\Users\CP\Documents\Visual
Studio 2010\Projects\D\STDS\NPC.d	252
Apr 02 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 04/03/2012 05:17 AM, Chris Pons wrote:

 I'm still having troubles with the min-heap.

 Node[] a;
 auto b = BinaryHeap!"a.fScore > b.fScore"( a[] );


 Error 1 Error: template instance BinaryHeap!("a.fScore >
 b.fScore") BinaryHeap!("a.fScore > b.fScore") does not match
 template declaration BinaryHeap(Store,alias less = "a < b") if
 (isRandomAccessRange!(Store) ||
 isRandomAccessRange!(typeof(Store.init[]))) C:\Users\CP\Documents\Visual
 Studio 2010\Projects\D\STDS\NPC.d 252


That is an API design issue. This should work:

auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);
Apr 03 2012
parent reply "Chris Pons" <cmpons gmail.com> writes:
Thanks, yes, that did work. However now when trying to insert 
nodes I get this error: Cannot grow a heap created over a range. 
I This is what I have:

Node[] a;
auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);
Node test, test2;
test2.fScore = 9;
test.fScore = 10;

b.insert( test );

I also tried this:

Node[2500] a;
auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);
Node test, test2;
test2.fScore = 9;
test.fScore = 10;

b.insert( test );

It gives the same error.
I also tried this:

Node[2500] a;
auto b = BinaryHeap!(Array!Node, "a.fScore > b.fScore")(a);
Node test, test2;
test2.fScore = 9;
test.fScore = 10;

b.insert( test );

Error	1	Error: this._store()[this._length()] is not an 
lvalue	C:\DLang\dmd2\src\phobos\std\container.d	2676	


How exactly would I grow this heap? or How would I give it enough 
room so that I don't need to make it larger?

On Tuesday, 3 April 2012 at 11:28:06 UTC, Timon Gehr wrote:

 On 04/03/2012 05:17 AM, Chris Pons wrote:

 I'm still having troubles with the min-heap.

 Node[] a;
 auto b = BinaryHeap!"a.fScore > b.fScore"( a[] );


 Error 1 Error: template instance BinaryHeap!("a.fScore >
 b.fScore") BinaryHeap!("a.fScore > b.fScore") does not match
 template declaration BinaryHeap(Store,alias less = "a < b") if
 (isRandomAccessRange!(Store) ||
 isRandomAccessRange!(typeof(Store.init[]))) 
 C:\Users\CP\Documents\Visual
 Studio 2010\Projects\D\STDS\NPC.d 252


 That is an API design issue. This should work:

 auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);
Apr 03 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Tuesday, 3 April 2012 at 19:38:12 UTC, Chris Pons wrote:

 Thanks, yes, that did work. However now when trying to insert 
 nodes I get this error: Cannot grow a heap created over a 
 range. I This is what I have: ...


Hey there,

BinaryHeap is using the "slice of memory" you're giving it to use 
as a heap. In the first code you gave, your array is length = 0. 
In other words, there is no place to actually insert things!

When you specified Node[2500] a, you are making an array of size 
2500 filled with zeros. You still don't have any room to insert, 
because all of the space in the array is still taken up.

Depending on your data, your option might be to just insert all 
the items you want first, then heapify the resulting array, maybe 
like this:
Node[] a;
foreach(i; 0..5) {
	Node nextNode;
	nextNode.fScore = (i*3) % 5;
	a ~= nextNode;
}
auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);

while(!b.empty()) {
	writeln(b.front());
	b.removeFront();
}

Otherwise, if you know a maximum bound for the number of inputs, 
you could simply allocate enough memory to store your items, and 
then use the initialSize parameter.
Something like this:
Node[] a;
// or Node[10] a; for a static array sized to 10...
a.length = 10;
// 0 states that nothing is in the heap
auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a, 0);
foreach(i; 0..5) {
	Node nextNode;
	nextNode.fScore = (i*3) % 5;
	b.insert(nextNode);
}
while(!b.empty()) {
	writeln(b.front());
	b.removeFront();
}

The thing you looked like you were doing with your third option 
looks like it was getting close to the right track for yet 
another potential solution, but apparently a bug prevents this 
from working: http://d.puremagic.com/issues/show_bug.cgi?id=6959
If this was working, then you could use Array for an unbounded 
input (because it supports insertBack).

I hope this helps!
Apr 03 2012
parent "Chris Pons" <cmpons gmail.com> writes:
Thanks! This clears up that part very well. I'm a lot closer to 
having a decent path finding algorithm now.

On Tuesday, 3 April 2012 at 21:24:24 UTC, Chris Cain wrote:

 On Tuesday, 3 April 2012 at 19:38:12 UTC, Chris Pons wrote:

 Thanks, yes, that did work. However now when trying to insert 
 nodes I get this error: Cannot grow a heap created over a 
 range. I This is what I have: ...


 Hey there,

 BinaryHeap is using the "slice of memory" you're giving it to 
 use as a heap. In the first code you gave, your array is length 
 = 0. In other words, there is no place to actually insert 
 things!

 When you specified Node[2500] a, you are making an array of 
 size 2500 filled with zeros. You still don't have any room to 
 insert, because all of the space in the array is still taken up.

 Depending on your data, your option might be to just insert all 
 the items you want first, then heapify the resulting array, 
 maybe like this:
 Node[] a;
 foreach(i; 0..5) {
 	Node nextNode;
 	nextNode.fScore = (i*3) % 5;
 	a ~= nextNode;
 }
 auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a);

 while(!b.empty()) {
 	writeln(b.front());
 	b.removeFront();
 }

 Otherwise, if you know a maximum bound for the number of 
 inputs, you could simply allocate enough memory to store your 
 items, and then use the initialSize parameter.
 Something like this:
 Node[] a;
 // or Node[10] a; for a static array sized to 10...
 a.length = 10;
 // 0 states that nothing is in the heap
 auto b = BinaryHeap!(Node[], "a.fScore > b.fScore")(a, 0);
 foreach(i; 0..5) {
 	Node nextNode;
 	nextNode.fScore = (i*3) % 5;
 	b.insert(nextNode);
 }
 while(!b.empty()) {
 	writeln(b.front());
 	b.removeFront();
 }

 The thing you looked like you were doing with your third option 
 looks like it was getting close to the right track for yet 
 another potential solution, but apparently a bug prevents this 
 from working: http://d.puremagic.com/issues/show_bug.cgi?id=6959
 If this was working, then you could use Array for an unbounded 
 input (because it supports insertBack).

 I hope this helps!
Apr 03 2012