Above is the Warrior deck that I put together to defeat Heroic Maexxna, after a couple attempts of dying with my Control Warrior deck I went to the net and tried out a couple decks that still didn't have enough finishing power for me to kill her. So I made some adjustments and came up with the deck above. It builds on the same premise as other Warrior decks for heroic Maexxna by filling the enemies side of the board with 1 attack minions and using Earthen Ring Farseer, Voodoo Doctor, and Armor Up! and canceling out the damage from the minions.
Where it differs from most is by using Leeroy and Molten Giant/Charge combo, just in case you don't get your charge cards, which is actually how I was able to finish her off with a free Molten Giant and 2 Charges on it for 16 damage. Using this deck only took me 2 attempts and you need to have the dexterity to sometimes forgo the heal armor move for a turn to make sure you can do damage to her through weapons. You will be low using this deck I hovered around 8 health the attempt I killed her.
Good luck Warriors.