Well, it's one of the rarest Pokemon that can be found on the Honey Trees. Just before Aipom and Munchlax. So it's kind of rare (I'm not sure if this helps in anyway, but I always found Heracross in the Honey Tree in the Floarama Meadow. I'm not sure if that's an individual thing, but check there I guess. xD)
Otherwise, it's quite rare.
Hope I helped. :)
Source: The Diamond and Pearl Walkthrough