It's the Pigeonhole Principle in the final step which is not constructively valid, not Heath-Brown's argument which, after inspection, doesn't show any of the tell tale signs of non-constructiveness.

Let $P_t$ be the set of all primes for which $t$ is a primitive root. Heath-Brown shows that if $q$, $r$, $s$ are three non-zero integers which are multiplicatively independent and that $q$, $r$, $s$, $-3qr$, $-3qs$, $-3rs$ and $qrs$ are not squares, then $P_q \cup P_r \cup P_s$ is infinite (and indeed that $\left|(P_q \cup P_r \cup P_s) \cap\lbrace1,\dots,x\rbrace\right| \gg x/(\log x)^2$). It is not constructively valid to draw from this the conclusion that one of $P_q$, $P_r$, $P_s$ is infinite.

One can see this using a Brouwerian counterexample which is analogous to the above situation. Let $A$ be the set of all $n$ for which there is a string of $333$ consecutive $3$'s in the first $n$ digits of $\pi$, and let $B$  be the complement of $A$. This is legitimate since I can always compute the first $n$ digits of $\pi$ to determine whether $n \in A$ or $n \in B$. Clearly $A \cup B = \lbrace1,2,3,\dots\rbrace$ is infinite. However, we cannot assert that $A$ or $B$ is infinite without knowing whether the digits of $\pi$ do or do not contain $333$ consecutive $3$'s. In the same way that GRH allows us to say that all three sets $P_q$, $P_r$, $P_s$ are infinite, the well-known conjecture that $\pi$ is normal allows us to assert that $A$ is infinite and $B$ is finite, but we don't know yet.

I haven't gone through Heath-Brown's argument in sufficient detail to assert without doubt that it is completely constructive but if there is a non-constructive part it must be hidden somewhere in some of the results he cites and not in the paper itself. In the paper, Heath-Brown *explicitly computes* an asymptotic lower bound on $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right|$. The argument is not straightforward but it is not convoluted and looks completely constructive. Instead of considering all primes, he considers a smaller but still large set of well-behaved primes $p$ for which he can break down the three multiplicative subgroups mod $p$ generated by $q$, $r$, $s$ into a handful of cases. He then computes upper bounds for the number of well-behaved primes up to $x$ falling into a case where none of $q,r,s$ are primitive roots. Adding these up and subtracting the result from a lower bound on the number of well-behaved primes up to $x$ gives $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right| \geq Cx/(\log x)^2$ where $C$ is a constant that may depend on $q, r, s$. Since the multiplicative subgroups of mod $p$ generated by $q$, $r$, $s$ are finite subgroups of a finite group, the various cases are decidable and it is fine to use the law of excluded middle to break into cases that way.