November 26, 2011

Binary Heaps in JavaScript Arrays

For the JavaScript A* path-finding project I'm working on, I needed to use binary heaps. I couldn't find any free code that was short and to the point, so I extended the native Array with two methods to do this: pushHeap and shiftHeap. Using these to add and remove items, you're ensured that the first item of the array will always have the lowest value. This comes in handy when it's too slow to sort thousands of items to find the lowest value. The implementation follows the description at