How to proof a heuristic?
According to Wikipedia:


  A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.


Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:


For optimization problems you may write something like:



  For any $\epsilon&gt;0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.


which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.


For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.




In any case you should keep in mind that a heuristic usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).