Thread overview | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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); |
Copyright © 1999-2021 by the D Language Foundation