A search for heavy resonances decaying into a $W$ or $Z$ boson and a Higgs boson produced in proton$-$proton collisions at the Large Hadron Collider at $\sqrt{s} = 13$ TeV is presented. The analysis utilizes the dominant $W \to q \bar{q}^\prime$ or $Z \to q \bar{q}$ and $H \to b \bar{b}$ decays with substructure techniques applied to large-radius jets. A sample corresponding to an integrated luminosity of 139 fb$^{-1}$ collected with the ATLAS detector is analyzed and no significant excess of data is observed over the background prediction. The results are interpreted in the context of the Heavy Vector Triplet model with spin-1 $W^\prime$ and $Z^\prime$ bosons. Upper limits on the cross section are set for resonances with mass between 1.5 and 5.0 TeV, ranging from 6.8 to 0.53 fb for $W^\prime \to WH$ and from 8.7 to 0.53 fb for $Z^\prime \to ZH$ at the 95 % confidence level.