I have tons of Heat Rocks. The way I got them was EV training for Speed on Route 8 and a lot of the times when I'd defeat a hoard of Wingull I'd get a Heat Rock fot it at the end. A message pops up at the end of the battle after you get the EXP so check your bag afterwards.
Grab a Pokemon with Sweet Scent and another with Heat Wave you need it in order for this to work. Head to Route 8 and defeat hoards of Wingull until you get it. It shouldn't take long at all.
There's also some other items you find in battle with unique moves.
Source.