you can do that as you want.
I was thinking this will require manual validation of a sample
In order to evaluate your heuristic results, you really need a manner to correctly classifies your data. This classification method should be more accurate as possible.
If a manual validation can devise such accuracy, then you can use it.
I want to know how good or bad my heuristic was
You need to verify the percentage of correct answers given by your heuristic.
To do so, you will need to compute the confusion matrix given by your heuristic, which will present the percentage of computed right and wrong answers.
You may also compare your labeling heuristic with other labeling methods from the literature. Therefore, you can compare the confusion matrix of both your labeling method and other methods from the literature to see which one performs better on your dataset.
There are several methods for comparing the confusion matrix of different algorithms. See this CV question and this paper for some discussion regarding this theme.
I do not know how big this sample should be
The manual validation of your data will probably be a hard and costly task. Therefore, you probably want to validate the minimum number of entries to get a valid statistical result.
Hence, the minimum sample size depends on how many methods you are comparing. If you are comparing two labeling methods (your's and a literature method) though a paired t-test, you can use the R function power.t.test. If you are comparing more than 2 labeling methods, you will need to compute the minimum sample size for that statistical test, see , , , , and .
P.S.: Despite my mention of the t-test, recall that you cannot use the t-test if your dataset does not meet their assumptions. You need to choose the correct statistical test to evaluate your data (which probably will not be the t-test).