Heating up the car before removing the sensor isn't the best idea. The sensor is made of 304 stainless, while the cat is made from 403 (or something close to it). The sensor will expand more then the cat and make removal more difficult.
Because of the stainless, neither thread should really be corroded but they could be stuck. Start off with a good penetrating oil a few days in advance (PB Blaster).
If you are confident, cut the wire off the old sensor before you remove it. This will allow you to use a standard socket instead of the more flexible and weak O2 sensor socket. Now you can put a honking-big breaker bar on there to get it loose, or use an impact wrench. If you have big hands then a set of crows foot sockets will make things easier.
When you reinstall, make sure to put anti-seize on the threads but keep it off the senor itself. I always use silver anti-seize but really you should use copper for a high temp area. The sensor is fairly tall so it may not fit a standard O2 socket without stressing the wire. This is when the big open ended wrench or crows foot comes in handy.