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

Posted in reply to Chris Pons | 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 | |
---|---|

Posted in reply to Justin Whear | ```
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 | |
---|---|

Posted in reply to Chris Pons | ```
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 | |
---|---|

Posted in reply to Justin Whear | ```
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 | |
---|---|

Posted in reply to Chris Pons | ```
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 | |
---|---|

Posted in reply to Henry Robbins Gouk | ```
> 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 | |
---|---|

Posted in reply to Henry Robbins Gouk | 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 | |
---|---|

Posted in reply to Chris Pons | ```
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 | |
---|---|

Posted in reply to Timon Gehr | ```
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 |
---|