There are several possible data structures to store the open-list. We could use an ArrayList to store the values and keep it sorted using an IComparable interface. With this solution we end up with too much overhead keeping the entire list sorted. After all, the only thing our pathfinder is interested in, is the node with the lowest F-score, it doesn’t care about the other nodes.
A better solution is using a binary heap. In a binary heap, each item has two children with a value higher or equal to itself. Which means in the end the lowest item is at the top of the heap, easily accessible.
One of the nice things of a binary heap is the fact that it can be stored in a 1-dimensional array, making sorting of the heap a very quick operation.
The top of the heap is always stored at index 1. We don’t use the 0-index when working with zero-based arrays.
The children of any given item are always stored at the item’s location * 2 and the item’s location * 2 + 1. For example, in the image given above, the item with value 20 is stored at index 3 and its two children can be found at index 6 (3 * 2) and index 7 (3 * 2 + 1).
Adding an item to a binary heap can be achieved by adding the new item at the end of the array and then letting the new item bubble its way up.
This is achieved by comparing the item with its parent, swapping them when the item is smaller then its parent and repeating this until the parent is smaller.
To remove an item from a binary heap, we simply take the item at index 1. But now we have to repair our heap, because there is a gap at the top. To fix this we take the last item and place it at the top, after which we let it sink downwards. This is done by comparing the value with its two children, replacing it with the smallest child and repeating this until the parent is smaller than both children.
A small comparison between an ArrayList and this binary heap implementation gives the following results:
Inspiration and some images used from Patrick Lester.