En heroico toca mirar youtube y google. Te dará una idea de como son los mazos que ganan.
Kelthuzad en heroico creo recordar que al principio de su turno activaba su poder que hace 4 de daño a todos tus minions. Usé un mazo de mago con únicamente minions con ultimo aliento (como el huevo que al morir te saca un 4/4), Feugen y Stalag, 2 duplicates para este combo y sacar hasta 3 bichos 11/11, Mirror Entity para controlar sus minions y muchas chispas. Tambien bichos con cargar para pegar el turno que entran.
El tema es que depende de las cartas que ya tengas para poder hacerte los heroicos. Si te compras Naxx entero, y no tienes muchas cartas, te propongo pasarte los normales y las pruebas esas especiales para tener cuantas más cartas de Naxx sea posible.