One God or many Gods is the not the definition of Heathen and Heretic in Christianity.
It appears to be that Islam believes all Abrahamic religions to have special protections so they may view all Abrahamic religions as heretics or the true faith.
However they do not believe that Zoroastrianism or One God faith in for example Tengrism or Native American faiths are heretics. They are heathens in Islam.
In Christianity the difference between heretic and heathen has been simple: do they believe Christ is the key to Salvation? 1) If yes then they are either a true believer or a heretic 2) if no then they are heathens.
If you read any medieval European literature that discusses Islam you can plainly see that Muslims 'mohammedans' are viewed as heathens just as bad as Norse or other polytheistic beliefs. Sometimes they are equated to being worse than heathens because they have heard the Word of God and twisted it. Whereas heathens may have never had the chance to lie about God's word.
That why in the end of my last paragraph I edited it and said :
The heathens or Pagans is polytheist. Which is totally different from monotheism. It could be applied to other monotheism religion that is different from Abraham Religion
I don't like to use Wikipedia as a source. But it can clear your mind:
Paganism (from classical Latin pāgānus "rural", "rustic", later "civilian") is a term first used in the fourth century by early Christians for people in the Roman Empire who practiced polytheism. This was either because they were increasingly rural and provincial relative to the Christian population, or because they were not milites Christi (soldiers of Christ). Alternate terms in Christian texts for the same group were hellene, gentile, and heathen. Ritual sacrifice was an integral part of ancient Graeco-Roman religion and was regarded as an indication of whether a person was pagan or Christian.
Paganism was originally a pejorative and derogatory term for polytheism, implying its inferiority. Paganism has broadly connoted the "religion of the peasantry". During and after the Middle Ages, the term paganism was applied to any unfamiliar religion, and the term presumed a belief in false god(s). Most modern pagan religions existing today (Modern or Neopaganism) express a world view that is pantheistic, polytheistic or animistic, but some are monotheistic.
Islam were viewed as heathen just for religious and political interests, nothing than that.
Heresy is any belief or theory that is strongly at variance with established beliefs or customs, in particular the accepted beliefs of a church or religious organization. The term is usually used in reference to violations of important religious teachings, but is also used of views strongly opposed to any generally accepted ideas. A heretic is a proponent of heresy.
And that why Catholics and Christian Navigators could not believed that people like Polynesians, Aztecs, Incas and other world indigenous groups could achieve the same level of knowledge as their home Nations (UK,Portugal,Spain, France).
If read the Jomini Post it could clarify the things for you.