Based on first-principles calculations and k·p models, we demonstrate that PbC/MnSe heterostructures are a non-Dirac type of Chern insulator with very large band gaps (244 meV) and exotically half-metallic edge states, providing the possibilities of realizing very robust, completely spin polarized, and dissipationless spintronic devices from the heterostructures. The achieved extraordinarily large nontrivial band gap can be ascribed to the contribution of the non-Dirac type electrons (composed of px and py) and the very strong atomic spin-orbit coupling (SOC) interaction of the heavy Pb element in the system. Surprisingly, the band structures are found to be sensitive to the different exchange and correlation functionals adopted in the first-principles calculations. Chern insulators with various mechanisms are acquired from them. These discoveries show that the predicted nontrivial topology in PbC/MnSe heterostructures is robust and can be observed in experiments at high temperatures. The system has great potential to have attractive applications in future spintronics.