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.

It's the Pigeonhole Principle in the final step which is not constructively valid, not Heath-Brown's main result 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. However, one can draw the more negative conclusion that $P_q$, $P_r$, $P_s$ are not all three finite.

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 we 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.