Mmmm tasty O(lg N)
This weekend, I’ve been looking at improving the scalability of some algorithms in one of our products at work. Today, I’ve replaced a linked list with a basic “priority queue”:http://www.nist.gov/dads/HTML/priorityque.html. It’s written, it compiles, and the most basic sanity tests now work without crashes. I’m happy 
Next step is to perform some more gruelling sanity tests, and load ‘er up with around 100,000 items to check if the change actually improved things. With O(lg N) worst-case addition and deletion–as opposed to the previous O(N)–I’m optimistic that it improves the situation. Have to see how performance is impacted for small numbers of items–hopefully performance loss at that end of the spectrum will be minimal.