Water trough heaters can work as long as they can't contact the edge of the pond and potentially melt it. My page on wintering ponds is at
http://www.fishpondinfo.com/winter.htm and should give you some ideas. A single de-icer would be enough to keep most of the pond open for most of the winter. I suggest adding an air stone. Not only does it keep a hole open better than just a heater but it aerates the water in winter.
What levels were 0 to 0.25? Ammonia? If so, in established ponds, ammonia should always be zero.
My pond algae page is at
http://www.fishpondinfo.com/plants/algae2.htm to give you some tips on that.
Good luck!
I love my fish too!