That an algorithm is heuristic does not preclude it from being provably correct.
It precludes it from being optimal!
The goal of an heuristic algorithm is to produce a near-optimal or approximate solution in a reasonable amount of time. From here, some heuristics have more or less theory behind them and that theory shows what sort of properties the solution has.