Both are correct: if you're not going to call him Ἡρακλῆς, then you need some way of representing his name in the Roman alphabet. Systems for doing this have changes over time.
The letter "k" fell out of use in Latin so, classically the letter kappa (κ) has been transliterated as "c", and this carried through to English. However, in the modern standard, designed by the Hellenic Organization for Standardization and adopted internationally by ISO, the UN and other organizations, kappa becomes "k".
In English, many people use a hybrid of the two systems. Because names such as Heracles, Cronos, Electra, Hecate and Socrates and places such as Crete, Cos, Corfu, Corinth, Macedonia and Attica are so well known under those spellings, they're always written that way in English. Similarly, words such as cycle, ecclesiastical and draconian also come from Greek words where kappas have been romanized as "c".
However, modern names and places that weren't well-known in English before the modern transliteration scheme are usually spelled with "k"s. If you look at a map of Greece labelled in English, you'll see lots of these: Heraklion, Kythira, Mykonos, Lefkada, etc. Always Constantine the Great, but usually Konstantinos Karamanlis (though sometimes Constantine Caramanlis).