Faits:
A.
X._, ressortissant bosniaque, né en 1982, est arrivé en Suisse le 4 janvier 2005. A la suite de son mariage, en février 2004, avec Y._, ressortissante serbe, titulaire d'une autorisation d'établissement dans le canton de Berne, il a obtenu une autorisation de séjour puis, le 13 janvier 2010, une autorisation d'établissement dans le canton de Neuchâtel, où les époux avaient annoncé leur arrivée le 1 er octobre 2007.
X._ a déposé une requête en divorce le 16 février 2010. Il a expliqué qu'il avait découvert que sa femme était enceinte d'un autre homme. Le divorce des époux a été prononcé le 11 mars 2010 par le Tribunal civil du district de Neuchâtel.
Le 29 novembre 2010, X._ a épousé dans son pays d'origine une compatriote, Z._ qui, le 7 décembre 2010, a déposé une demande de visa de long séjour à l'ambassade de Suisse de Sarajevo pour venir rejoindre son mari. Cette demande concernait également son fils A._, né le 20 février 2008, dont le père est X._. Ce dernier a expliqué au Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) qu'il avait eu une relation occasionnelle avec sa seconde épouse en mai 2007, qu'il était retourné en Bosnie-Herzégovine pour reconnaître l'enfant, mais n'avait plus eu de contact avec cette dernière jusqu'aux vacances d'été 2010, où ils avaient décidé de se marier. Le 7 juin 2011, il a également signalé que son épouse avait accouché d'un second enfant.
B.
Par décision du 28 juin 2011, le Service des migrations a révoqué l'autorisation d'établissement de X._ et lui a imparti un délai au 31 août 2011 pour quitter la Suisse. Il a également classé les demandes de regroupement familial déposées en faveur de Z._ et A._.
Dans un recours du 16 août 2011, X._ a fait état de l'altération de son état de santé à la suite de la décision du 28 juin 2011 et a demandé la révocation des mesures d'expulsion jusqu'à nouvel avis du médecin.
Par décision du 9 mars 2012, le Département de l'économie du canton de Neuchâtel (ci-après: le Département) a constaté que X._ ne contestait pas les motifs ayant présidé à la révocation de l'autorisation d'établissement. Il a estimé que seule la question de l'existence d'un cas individuel d'extrême gravité devait être examinée et que les conditions pour reconnaître la réalisation d'un tel cas sous l'angle médical n'étaient pas remplies. Au sujet des autres critères, il a notamment retenu que l'intéressé n'avait pas " respecté l'ordre juridique suisse en se prévalant d'une situation maritale qui n'existait plus que formellement pour obtenir son autorisation d'établissement, dissimulant par la même occasion la constitution d'une famille parallèle en Bosnie. "
X._ a recouru contre cette décision auprès du Tribunal cantonal du canton de Neuchâtel, Cour de droit public, qui, par arrêt du 23 mai 2013, a rejeté le recours. La juridiction cantonale a considéré en bref que, dans la mesure où le recourant avait invoqué uniquement son état de santé et son statut de travailleur dans son " mémoire de recours du 16 août 2011 ", le Département n'avait pas à examiner les motifs sur lesquels s'était fondé le Service de la population pour révoquer l'autorisation d'établissement. Il en a déduit que seul l'examen d'un cas individuel d'extrême gravité pouvait faire l'objet du recours, mais qu'aucune autorisation de séjour ne pouvait être accordée au recourant à ce titre.
C.
Agissant par la voie du recours en matière de droit public, subsidiairement du recours constitutionnel subsidiaire, X._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 23 mai 2013. Il demande au Tribunal fédéral, à titre principal, de constater qu'il n'a pas commis un abus de droit en invoquant son mariage avec Mme Y._ et, par conséquent, de maintenir son autorisation d'établissement. A titre subsidiaire, il requiert le Tribunal fédéral de constater qu'il se trouve dans la situation d'un cas individuel d'extrême gravité et, partant, de lui accorder une autorisation de séjour.
Le Tribunal cantonal se réfère à son arrêt et conclut au rejet du recours, de même que le Service des migrations qui estime " que les griefs soulevés par le recourant ont déjà été examinés par les différentes autorités de recours cantonales ". De son côté, le Département se réfère aux considérants de l'arrêt attaqué et conclut au rejet du recours dans la mesure où il est recevable. L'Office fédéral des migrations propose le rejet du recours.

Considérant en droit:
1.
1.1. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est cependant recevable contre la décision révoquant l'autorisation d'établissement du recourant, car il existe en principe un droit au maintien de cette autorisation (<ref-ruling> consid. 1.2.1 p. 4).
Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>, le présent recours est donc en principe recevable comme recours en matière de droit public en tant qu'il porte sur la révocation de l'autorisation d'établissement du recourant.
1.2. En revanche, d'après l'art. 83 let. c ch. 5 LTF, le recours en matière de droit public n'est pas recevable contre les décisions qui concernent les dérogations aux conditions d'admission. Il s'ensuit que le présent recours est irrecevable comme recours en matière de droit public en tant qu'il conclut à l'octroi d'une autorisation de séjour fondée sur l'art. 30 al. 1 let. b de la loi fédérale sur les étrangers (LEtr; RS 142.20), pour cas individuel d'extrême gravité. Reste à déterminer si ce point peut être traité par la voie du recours constitutionnel subsidiaire (<ref-law>) déposé par le recourant.
La qualité pour former un tel recours suppose toutefois un " intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Or, le recourant ne peut pas se prévaloir de l'art. 30 al. 1 let. b LEtr, au vu de la formule potestative de cette disposition qui ne lui confère pas une position juridique protégée pour agir au fond (cf. arrêt 2D_10/2013 du 13 mars 2013, consid. 3). Quant à la violation de ses droits de partie équivalant à un déni de justice formel, pour autant qu'il s'agisse de moyens pouvant être séparés du fond (cf. ATF 133 I 185 consid. 6 p. 198 ss), ils peuvent de toute façon être examinés dans le cadre du recours en matière de droit public. Partant, le présent recours est irrecevable comme recours constitutionnel subsidiaire (<ref-law>).
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, y compris la violation des droits fondamentaux (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation de l'<ref-law>. En outre, le Tribunal fédéral fonde son raisonnement juridique sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou incomplète - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 7.1 p. 51) - ou encore en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (cf. <ref-ruling> consid. 3 p. 104; arrêt 2C_990/2012 du 7 mai 2013 consid. 3.2).
3.
Le recourant fait valoir une violation du droit fédéral au sens de l'<ref-law>, subsidiairement une violation des droits constitutionnels, en particulier des principes du droit d'être entendu, de la bonne foi et de l'interdiction de l'arbitraire. Il reproche essentiellement au Tribunal cantonal de n'avoir pas examiné les motifs ayant présidé à la révocation de son autorisation d'établissement et soutient que la juridiction cantonale aurait ainsi établi les faits de façon manifestement inexacte et en violation du droit au sens de l'<ref-law> (<ref-law>).
3.1. Le Tribunal cantonal a estimé que l'art. 43 al. 1 de la loi cantonale sur la procédure et la juridiction administratives (LPJA; RSNE 152.30), prévoyant que l'autorité de recours n'est pas liée par les motifs invoqués à l'appui du recours, n'impliquait pas un contrôle de la décision attaquée sous tous ses aspects, mais uniquement un examen des points effectivement litigieux. Il en a déduit que, dans la mesure où le recourant n'avait invoqué que son état de santé et son statut de travailleur pour s'opposer à son renvoi de Suisse, le Département n'avait pas à examiner les motifs sur lesquels s'était fondé le Service des migrations pour révoquer l'autorisation d'établissement de l'intéressé. Par conséquent, la cour cantonale a elle-même limité son examen au cas individuel d'extrême gravité au sens de l'art. 30 al. 1 let. b LEtr, considérant que le bien-fondé de la révocation de l'autorisation d'établissement ne faisait plus partie de la contestation portée devant lui.
3.2. La jurisprudence a déduit du droit d'être entendu (art. 29 al. 2 Cst.) le devoir pour le juge de motiver sa décision, afin que le justiciable puisse la comprendre, la contester utilement s'il y a lieu et exercer son droit de recours à bon escient. Pour répondre à ces exigences, le juge doit mentionner, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. Il n'a toutefois pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 2.2 p. 84; <ref-ruling> consid. 5.1 p. 237 et les arrêts cités). Dès lors que l'on peut discerner les motifs qui ont guidé la décision de l'autorité, le droit à une décision motivée est respecté même si la motivation présentée est erronée. La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (arrêts 2C_23/2009 du 25 mai 2009 consid. 3.1, in RDAF 2009 II p. 434; 1C_246/2013 du 4 juin 2013 consid. 2.1). Une autorité se rend coupable d'une violation du droit d'être entendu si elle omet de se prononcer sur des griefs qui présentent une certaine pertinence ou de prendre en considération des allégués et arguments importants pour la décision à rendre (<ref-ruling> consid. 5.2 p. 248; <ref-ruling> consid. 2b p. 102 ss).
En l'espèce, le Tribunal cantonal n'a pas omis de se prononcer sur les griefs relatifs à la révocation de l'autorisation d'établissement du recourant, mais a clairement expliqué les motifs pour lesquels il considérait que ce point ne pouvait plus être contesté devant lui et qu'il n'avait pas à l'examiner d'office. Ce faisant, il n'a pas violé le droit d'être entendu du recourant. Reste à déterminer si son argumentation est ou non fondée au regard des griefs d'arbitraire et de violation du principe de la bonne foi soulevés par le recourant.
3.3. Une décision est arbitraire lorsqu'elle contredit clairement la situation de fait, lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 7.1 et les arrêts cités).
3.3.1. L'art. 43 LPJA dispose que:
"1. L'autorité de recours n'est pas liée par les motifs invoqués à l'appui du recours.
2. Les constatations de fait ne lient pas l'autorité de recours.
3. L'autorité de recours n'est pas liée par les conclusions des parties; elle peut réformer, au détriment du recourant, la décision attaquée ou accorder plus que le recourant n'avait demandé; elle doit cependant donner aux parties l'occasion de se prononcer ou de retirer les recours. "
Il ressort expressément de cette disposition que les autorités de recours ne sont pas liées par les motifs, ni par les conclusions des parties, contrairement à la procédure devant le Tribunal fédéral où les conclusions des parties déterminent, avec la décision attaquée, l'objet de la contestation (cf. <ref-law>; arrêt 2C_649/2013 du 16 juillet 2013 consid. 4 et les arrêts cités). On ne voit donc pas que le Tribunal cantonal ait pu, sous peine de tomber dans l'arbitraire, confirmer le bien-fondé du refus du Département d'entrer en matière, puis faire de même, au motif que, devant le Département, le recourant n'avait pas contesté la révocation de son autorisation d'établissement.
Un tel raisonnement est d'autant plus inadmissible que l'acte qualifié de " recours devant le Département du 16 août 2011 " par le Tribunal cantonal n'est en réalité qu'une simple lettre du recourant lui-même, adressée au Service de la population. Celui-ci a transmis ce courrier au Département en tant que recours, tout en relevant qu'il était " quelque peu difficile à comprendre " et que l'intéressé semblait " demander l'annulation de notre décision ." Si le Département avait des doutes quant au fait que ledit courrier demandait bien l'annulation de la décision dans son entier, il lui appartenait, conformément aux règles de la bonne foi et comme le prévoit du reste aussi l'art. 35 al. 3 LPJA, d'impartir un délai convenable au recourant pour compléter son recours. Le recourant s'en est du reste plaint dans son recours devant le Tribunal cantonal, mais celui-ci n'en a pas tenu compte.
Enfin, la décision du Département fait elle-même allusion aux motifs ayant justifié la révocation de l'autorisation d'établissement. En effet, lors de l'examen des conditions pour reconnaître l'existence d'un cas d'extrême gravité, le Département a retenu que le recourant n'avait pas respecté l'ordre juridique suisse en se prévalant abusivement de de son mariage qui n'existait plus que formellement pour obtenir une autorisation d'établissement.
3.3.2. En pareilles circonstances, le Tribunal cantonal a restreint de manière insoutenable son pouvoir d'examen en refusant de se prononcer sur le bien-fondé de la révocation de l'autorisation d'établissement du recourant au motif que, dans sa lettre qui tenait lieu de recours devant le Département, l'intéressé n'avait pas contesté ce point. Cette approche aboutit aussi à un résultat arbitraire, dès lors que l'arrêt attaqué a précisément pour effet de confirmer la révocation de l'autorisation d'établissement du recourant, sans que les éléments déterminants et les griefs du recourant n'aient été examinés. Il appartient partant aux juges cantonaux de se prononcer sur cet aspect.
3.4. A cela s'ajoute que, selon l'<ref-law>, l'autorité qui précède immédiatement le Tribunal fédéral doit pouvoir examiner au moins les griefs visés aux art. 95 à 98 LTF, soit notamment la violation de l'un des droits inclus à l'<ref-law>, dont la LEtr et les règles sur le mariage abusif à l'origine de la révocation de l'autorisation d'établissement du recourant font partie. La limitation du pouvoir d'examen que s'est imposée le Tribunal cantonal est donc également contraire à l'<ref-law>.
4.
Au vu de ce qui précède, le recours doit être admis et l'arrêt attaqué annulé, sans qu'il soit nécessaire d'examiner encore les autres griefs soulevés par le recourant. La cause sera ainsi renvoyée au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
Le présent arrêt est rendu sans frais (<ref-law>). Le canton de Neuchâtel devra verser au mandataire du recourant une indemnité à titre de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours en matière de droit public est admis dans la mesure où il est recevable et l'arrêt attaqué est annulé.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
L'affaire est renvoyée au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
4.
Il n'est pas perçu de frais judiciaires.
5.
Le canton de Neuchâtel versera au mandataire du recourant une indemnité de 2'000 fr. à titre de dépens.
6.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations et au Département de l'économie du canton de Neuchâtel, au Tribunal cantonal de la République et canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 20 novembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat