Thursday, November 12, 2009

Code Reuse

So here is a pretty useful trick/hack.
Say you need to create a max-heap. However, the code that you are forced to use will only create a min-heap. What do you do?
Well one solution is to just negate all the input entries, and then create a min-heap. Then the most negative (or most positive depending on how you view things) will be at the top.

I used this trick on my last Data Structures homework assignment. The code that we were allowed to use would create a tree with the smallest element as the root. But we needed to find the largest element. Now I could have easily written my own code, but why should I when code has already been provided? So all I had to do was negate the input and then copy the given code (though I did have to change a few inequalities around). Overall it was a great feeling, like I was "beating the system".
I prefer to look at this as being creative and not as being lazy.

Sadly, I can't take all the credit for this method. I had seen it before while reading a TopCoder tutorial on the C++ STL. They were talking about how to implement Dijkstra's algorithm with a priority queue. In C++ the priority queue container will always put the largest element at the top by default (though you can easily change this).