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

- "Chris Pons" <cmpons gmail.com> Apr 02 2012
- Justin Whear <justin economicmodeling.com> Apr 02 2012
- Timon Gehr <timon.gehr gmx.ch> Apr 03 2012
- "Chris Pons" <cmpons gmail.com> Apr 02 2012
- Justin Whear <justin economicmodeling.com> Apr 02 2012
- "Chris Pons" <cmpons gmail.com> Apr 02 2012
- "Henry Robbins Gouk" <henry.gouk gmail.com> Apr 02 2012
- "Henry Robbins Gouk" <henry.gouk gmail.com> Apr 02 2012
- "Chris Pons" <cmpons gmail.com> Apr 02 2012
- "Chris Pons" <cmpons gmail.com> Apr 03 2012
- "Chris Cain" <clcain uncg.edu> Apr 03 2012
- "Chris Pons" <cmpons gmail.com> Apr 03 2012

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

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

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

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

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

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

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

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

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

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

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

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