The photonic-band-gap (PBG) structures of two-dimensional magnetic photonic crystals (MPCs) are investigated by using the plane wave expansion (PWE) method. One is composed of rectangular magnetic pillars embedded into host dielectric in rectangular lattice (RR type), the other consists of circle magnetic cylinders embedded into host dielectric in triangular lattices (TC type). The changes of PBG structures corresponding to the magnetic permeability are presented, and each sample is found with large ratio of gap-midgap. Based on the above results, the PBG structure of magnetic heterostructures composed of both RR type and TC type MPCs (MRRTC heterostructures) is investigated by use of PWE method combined with the supercell technique. The guide modes at the interface of MRRTC heterostructures are produced at absolute PBG without longitndinal gliding or displacement of the lattice. When introducing the relatively longitudinal gliding and transverse displacement of the lattice from the interface, the dispersion curves of guide modes vary apparentely.