there is one parameters that people tend to ignore. Linear regulators dissipate the rest power as heat (thats why they are not very efficient). What this means is that if you provide lets say 12 volts and you get 5, then there is an amount of power that has to be dissipated to get your 5 volts. To calculate this, you subtract the 5 from 12 and then multiply by the current drawn. Suppose that you circuit draws 0.5A (500mA), and you power from 12 V:
Vdif = 12 - 5 = 7V
Pdis = 7 x 0.5 = 3.5 Watts
From my experience i can tell you that 3.5 Watts of power dissipated will make the 7805 to fry within one minute. You'll get a bad burn if you touch it.
So, what to do: first measure the current drawn, the MAX current drawn. Then, use 2W resistors to drop the excess of power. In the previous example, i would try to dissipate the 3.5W of heat into 4 elements, 3 resistors and the 7805. This way, each one would have to dissipate some 1.1 watts. To calculate the resistors, you reverse the P=I^2xR formula like this:
R = P / I2 = > R = 1.1 / 0.52 => R = 4.4 Ohms
So i would put 3 resistors in series before the 7805, each resistor is 5Ohms 2 (or more) watts
Obviously, the 500mA that you mention is not a real value, because as i said, 4 watts are TOO much. So you need to precisely measure your MAX current
Solution 2: Use an SMPS buck regulator... And problem solved... It is not as simple as the 7805, but it will dissipate only a fraction of the power provided
Solution 3: Use a smaller voltage as a main supply. If for example you use 6.5 volts to drop them down to 5, the power dissipation is:
1.5 x 0.5 = 0.75 Watts
A small heatsink is enough to dissipate this power.