Follow up Question from: https://codereview.stackexchange.com/questions/30243/how-can-i-improve-upon-my-a-pathfinding-code/
Summary: I asked for help improving my pathfinding code (A*). A user quickly spotted that I was sorting a particular list of nodes a lot and that using IComparible to do so - Apparently very inefficient. He suggested using an OrderedBag, however, I have to code everything myself and can't use code from the internet.
The Question: So, would making a Binary Heap be the most effective way of maintaining ordered data, while still being able to add and remove data quickly. If so, does anyone have any links to point me in the right direction for creating one, and which one to create?
I've heard of a LinkedList - Good idea?
If you are rolling your own as an exercise then yes, a heap is the correct data structure to build an efficient priority queue. Start with a binary heap because its fairly easy. You can always try a more complex heap later if you have time and inclination.
Questions recommending off site resources are off topic btw. The standard print source for simple algorithms and data structures is Introduction to Algorithms. But these days Wikipedia is a good source for pseudo code as well. (Note that the Wikipedia article shows how to build a max heap; you need a min heap. Figuring out how to build a min heap given the code for a max heap is a good exercise.)
This article also gives some good advice on use of binary heaps for
A*.