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?

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

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

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 );

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.

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.

> 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.

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	

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);

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);