A second important feature of a heuristic is how much time it takes to run on a computer. Remember that one important reason to use a heuristic is that finding an optimal solution takes too long. This is particularly true for problems with integer programming formulations. It does no good to create a heuristic if it too will take to long to solve.
One common example of this problem occurs in exchange heuristics. Removing k variables and adding k others to a solution seems a practical method for getting good quality solutions. The higher the k value, the better solutions. As k gets large, however, the amount of time required to check all ways of removing k items and adding k others grows quickly. Even for values like 4 and 5, it is generally too time consuming to do such exchanges.
A further advantage of very short execution times is that multiple runs can be done in a short amount of time. If the heuristic has a randomized portion, then multiple runs can be done of that heuristic. Otherwise, it can be combined with other fast heuristics and only the best of them is taken. This is particularly true if the heuristic is combined with a fast improvement heuristic.