Overheating, possible 02 sensor issue

No. Lets clear up some confusion first. The diagnostic fault code you got did not say to replace the oxygen sensor. Fault codes never ever say to replace parts or that one is bad. When a part is referenced in a fault code, it only indicates the circuit or system that needs further diagnosis, or an unacceptable operating condition. The part listed is only the cause of the problem about half of the time. There are well over a dozen fault codes related to oxygen sensors and they mean very different things. If you know the exact code number, you can go here:

https://www.2carpros.com/trouble_codes/obd2

To see a list of the definitions, or I can interpret it for you.

The Engine Computer only looks at the front oxygen sensor readings to fine tune the fuel metering calculations, and only once the engine is warmed up. Its readings actually have about the least effect on the fuel mixture of most of the engine sensors. A defective oxygen sensor won't cause engine overheating either, but it is possible to have a problem that lends itself to overheating and causes a fuel-related problem that is detected by the oxygen sensor which sets a fault code. We can figure that out once we know the code number.

For the overheating, did that occur at highway speed or only at slow speeds when the radiator fan is needed? Can you hear if the fan is turning on?

Also consider looking at these articles for more information:

https://www.2carpros.com/articles/engine-cooling-system

https://www.2carpros.com/articles/how-an-electric-cooling-fan-works

That code refers to the oxygen sensor's heater circuit. It could indeed be caused by a defective sensor, but it is just as likely to be caused by corrosion on a connector terminal, a cut wire, or water in the connector that caused a fuse to blow. Also look for a wire harness that fell down onto hot exhaust parts.

Lets start with the easiest thing to check. I can only find two fuses related to the O2 sensors. Those are SBF-5 and SBF-7, both 30-amp, in the under-hood fuse box. Check for 12 volts on both sides of both fuses with the engine running. If you find 12 volts on one side of a fuse and 0 volts on the other side, that fuse is blown.

At the mileage you listed, it is a little early to be thinking about a leaking cylinder head gasket, but given your observation the engine overheats in just a few minutes, that is a good suspect. An engine cannot overheat that quickly otherwise when started cold. The best test for this involves drawing air from the radiator, with the engine running, through a glass cylinder with two chambers partially-filled with a special dark blue liquid. If combustion gases are sneaking into the cooling system, the liquid will turn bright yellow. Those gases can pool under the thermostat, preventing it from opening. Thermostats must be hit with hot liquid to open. Hot air will not do it.

It only takes a few minutes for your mechanic to perform this test. You can also borrow the tester from an auto parts store that rents or borrows tools, but they will make you buy your own bottle of fluid. That is because it is rendered ineffective if it freezes or if it becomes contaminated with coolant. They do not want to risk borrowing the tool to you after the last person contaminated the fluid, so they made them buy their own too. Due to the cost of the fluid, it might be less expensive to just have your mechanic do the test.

Here is some articles that may offer more information:

https://www.2carpros.com/articles/how-a-car-fuse-works

https://www.2carpros.com/articles/how-to-use-a-voltmeter