View mode: basic / threaded / horizontal-split · Log in · Help
April 02, 2012
Min-Heap and Hash Table help
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?
April 02, 2012
Re: Min-Heap and Hash Table help
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
April 02, 2012
Re: Min-Heap and Hash Table help
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
April 02, 2012
Re: Min-Heap and Hash Table help
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 );
April 02, 2012
Re: Min-Heap and Hash Table help
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.
April 03, 2012
Re: Min-Heap and Hash Table help
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.
April 03, 2012
Re: Min-Heap and Hash Table help
> 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.
April 03, 2012
Re: Min-Heap and Hash Table help
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
April 03, 2012
Re: Min-Heap and Hash Table help
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);
April 03, 2012
Re: Min-Heap and Hash Table help
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);
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home