Hey guys, here are the decks I used to beat the thee first bosses in heroic mode.
Anub´Rekhan:
Normal MR-deck, relatively easy to handle.
Faerlina:
Zoo-Deck for spamming Monsters because of her passive.
If she can´t use her passive good, she´s weak.
Maexxna:
I did her with this deck.
The main thing is to clear the board when it´s full (Blizzard, Flamstrike) and play cards that let you draw cards.
Do not deal too much dmg in her face, because if you got it to 9 mana, Alex is the way to win.
Before you do this, get some Mobs on your side of the Battlefield, Giants, whisps, everything that costs low mana then, spam EVERYTHING possible.
Next turn Alex will set Maexxna´s HP to 15 and you can finish her.
This deck took me ~8 trys to beat her up, maybe you finish her earlier.
Best of Luck,
steameroo