In this paper, a new heterostructure phononic crystal is introduced. The new heterostructure is composed of square and rhombus phononic crystals. Using finite difference method, a displacement-based algorithm is presented to study elastic wave propagation in the phononic crystal. In contrast with conventional finite difference time domain method, at first by using constitutive equations and strain-displacement relations, elastic wave equations are derived based on displacement. Then, these forms are discretized using finite difference method. By this technique, components of stress tensor can be removed from the updating equations. Since the proposed method needs less elementary arithmetical operations, its computational cost is less than that of the conventional FDTD method. Using the presented displacement-based finite difference time domain algorithm, square phononic crystal, rhombus phononic crystal and the new heterostructure phononic crystal were analyzed. Comparison of transmission spectra of the new heterostructure phononic crystal with those creating lattices, showed that band gap can be extended by using the new structure. Also it was observed that by changing the angular constant of rhombus lattice, a new extended band gap can be achieved.