Getting Heart Scales is easy, just start Thief-killing a ton of Luvdisc.
Just the concept of it is hilarious though. Here is a warm, happy underwater village of kissing fish in the shape of hearts when suddenly a crazed, demonic pokemon trainer appears and starts fishing them up out of the water and having his powerful Level 35 Thief Mightyena (tm) ripping the heart scales out from between their pink films and eyes and chest cavities or wherever the hell else they keep those things.
In minutes an entire Luvdisc civilization is decimated, bodies everywhere as the trainer walks away with fistfuls of heart scales to give to some obsessed heart-scale collector. And for what? So his even more badass pokemon can learn some shitty move it didn't even care enough to remember in the first place.