Faits :
A.
A.a. A._, ressortissant albanais né en 1983, a séjourné illégalement sur le territoire helvétique à plusieurs reprises depuis 1999. Il a fait l'objet de décisions de renvoi notamment en septembre 1999, août 2001, juillet 2002, octobre 2003 et mai 2011. Malgré une interdiction d'entrée, prononcée en 2005 pour une durée indéterminée, A._ est revenu en Suisse en 2011 et n'a plus quitté ce pays. Le 9 septembre 2012, il est devenu père d'une fille, B._, qui est ressortissante suisse. Il l'a reconnue le 13 janvier 2013.
A.b. A._ a été condamné à de multiples reprises en Suisse et, notamment, le 29 septembre 2003 à une peine privative de liberté de treize mois, le 7 mars 2011 à une peine privative de liberté de dix-huit mois et le 12 septembre 2013 à une peine privative de liberté de trois ans, suspendue au profit d'un traitement institutionnel des addictions. Ces peines sanctionnent essentiellement des infractions à la législation sur les étrangers et à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (LStup; RS 812.121). Détenu à partir d'octobre 2015, A._ a fait l'objet d'une nouvelle condamnation le 28 septembre 2016, à une peine privative de liberté d'ensemble de 30 mois pour crime et délit contre la LStup. Les infractions ont été commises entre novembre 2014 et octobre 2015.
A.c. A la suite de la naissance de sa fille, A._ a sollicité une autorisation de séjour par regroupement familial auprès des autorités bernoises. Le 12 novembre 2015, le Tribunal administratif du canton de Berne a confirmé le refus d'octroi de cette autorisation et a prononcé le renvoi de Suisse de A._. Cette autorité a notamment relevé que l'état de santé du recourant, qui est atteint du syndrome de Brugada de type 2, une maladie entraînant des troubles du rythme cardiaque, et porte un défibrillateur automatique implantable depuis juin 2013, ne s'opposait pas à son renvoi. Elle a par ailleurs jugé, au sujet de l'allégation d'un risque de représailles meurtrières par une famille ennemie (Vendetta selon le code kanun), qu'un danger sérieux et actuel n'était pas établi (cf. art. 105 al. 2 LTF).
A.d. La mère de B._ est décédée le 24 mai 2016. Par décision de l'Autorité de protection de l'enfant et de l'adulte (ci-après: l'Autorité de protection) du 7 juillet 2016, l'enfant a été placée chez sa grand-mère maternelle avec l'accord de son père et un curateur a été nommé. A._ conserve l'autorité parentale. L'Autorité de protection a renoncé à prononcer le retrait formel du droit de garde (cf. art. 105 al. 2 LTF).
B.
Le 26 janvier 2017, alors qu'il était détenu à U._, A._ a déposé auprès du Service des migrations du canton de Neuchâtel (ci-après: le Service cantonal) une (nouvelle) demande d'autorisation de séjour. Le 5 mai 2017, il a confirmé sa demande et requis l'admission provisoire à titre subsidiaire.
Par décision du 17 août 2017, le Service cantonal a rejeté la demande d'autorisation de séjour, qu'il a traitée comme une requête de reconsidération de la demande définitivement jugée le 12 novembre 2015, a refusé de transmettre le dossier au Secrétariat d'Etat aux migrations et a ordonné à A._ de quitter le territoire neuchâtelois à sa libération. Saisi d'un recours contre ce prononcé, le Département de l'économie et de l'action sociale du canton de Neuchâtel (ci-après: le Département) l'a rejeté par décision du 18 janvier 2018. Contre cette décision, A._ a formé un recours à la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel (ci-après: le Tribunal cantonal).
Le 17 avril 2018, il a été libéré.
Par arrêt du 11 octobre 2018, le Tribunal cantonal a rejeté le recours.
C.
Agissant par la voie du recours en matière de droit public et celle, subsidiaire, du recours constitutionnel, A._ demande au Tribunal fédéral, sous suite de frais et dépens, principalement l'annulation de l'arrêt du 11 octobre 2018 du Tribunal cantonal et l'octroi d'une autorisation de séjour et, subsidiairement, le renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il requiert l'assistance judiciaire et l'effet suspensif, ainsi que, à titre de mesure provisionnelle, l'octroi de l'autorisation de séjour sollicitée pour la durée de la procédure.
L'effet suspensif a été accordé par ordonnance présidentielle du 15 novembre 2018.
Le Service cantonal, le Département, ainsi que le Tribunal cantonal concluent au rejet du recours. Le Secrétariat d'Etat aux migrations n'a pas déposé d'observations.
Considérant en droit :
1.
Le recourant a déposé, dans un même acte (cf. art. 119 LTF), un recours en matière de droit public et un recours constitutionnel subsidiaire. La recevabilité du premier excluant celle du second (cf. art. 113 LTF), il convient d'examiner en priorité si la voie du recours en matière de droit public est ouverte.
1.1. Le recourant s'en prend au refus d'autorisation de séjour confirmé par le Tribunal cantonal.
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 (art. 83 let. c ch. 2 LTF). En l'occurrence, le recourant, qui se prévaut de la relation avec sa fille de nationalité suisse, fait valoir de manière défendable un droit à l'octroi d'une autorisation de séjour fondé sur l'art. 8 CEDH, de sorte que son recours échappe à la clause d'irrecevabilité de l'art. 83 let. c ch. 2 LTF (cf. arrêt 2C_652/2013 du 17 décembre 2013 consid. 1.1 non publié in ATF 140 I 145). La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (cf. ATF 139 I 330 consid. 1.1 p. 332).
Au surplus, le recours, dirigé contre une décision finale (art. 90 LTF) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF), a été déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites (art. 42 LTF), par le destinataire de l'arrêt attaqué, qui a la qualité pour recourir (art. 89 al. 1 LTF). Il est partant recevable en tant que recours en matière de droit public s'agissant du refus de l'autorisation de séjour. Il s'ensuit que le recours constitutionnel subsidiaire est irrecevable sur ce point.
1.2. Le recourant reproche également à l'autorité précédente de ne pas avoir retenu un cas de rigueur au sens de l'art. 30 al. 1 let. b LEtr (RS 142.20; dont le titre s'intitule depuis le 1 er janvier 2019 loi fédérale sur les étrangers et l'intégration [RO 2017 6521]); ci-après: LEI). Son grief est irrecevable dans le cadre du recours en matière de droit public, car cette disposition ne confère aucun droit et relève des dérogations aux conditions d'admission, expressément exclues de cette voie de droit (cf. 83 let. c ch. 5 LTF; cf. arrêt 2C_689/2017 du 1er février 2018 consid. 1.2.1). Seul un recours constitutionnel subsidiaire serait ouvert. 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 (art. 115 let. b LTF). Or, le recourant, qui ne peut se prévaloir de l'art. 30 al. 1 let. b LEI au vu de sa formulation potestative, n'a pas une position juridique protégée lui conférant la qualité pour agir au fond sous cet angle (cf. ATF 133 I 185 consid. 6.1 p. 197 s.; arrêt 2D_39/2018 du 18 décembre 2018 consid. 1.2). Même s'il n'a pas qualité pour agir au fond, le recourant peut se plaindre par la voie du recours constitutionnel subsidiaire de la violation de ses droits de partie, pour autant qu'il ne s'agisse pas de moyens ne pouvant être séparés du fond (cf. ATF 133 I 185 consid. 6 p. 198 s.; arrêt 1B_282/2018 du 31 octobre 2018 consid. 1.4). Le recourant ne fait toutefois pas valoir de tels griefs en l'occurrence, de sorte que, sous cet angle également, il n'y a pas lieu d'entrer en matière sur le recours constitutionnel subsidiaire en lien avec l'art. 30 al. 1 let. b LEI (cf. arrêt 2C_289/2017 du 4 décembre 2017 consid. 1.4).
1.3. Le recourant, qui mentionne l'art. 3 CEDH, estime en outre que son renvoi est inexigible et illicite, car il ne pourrait, selon lui, pas recevoir les soins nécessaires pour traiter ses problèmes cardiaques et encourrait la vengeance d'une famille ennemie de la sienne dans son pays d'origine. Ce grief ne peut pas non plus être examiné dans le cadre du recours en matière de droit public (cf. art. 83 let. c. ch. 4 LTF) et relève en principe du recours constitutionnel subsidiaire (cf. ATF 137 II 305 consid. 1.1 p. 307; arrêt 2C_204/2018 du 9 septembre 2018 consid. 1.3). En l'espèce, les griefs du recourant se confondent toutefois avec le contrôle de proportionnalité du refus de l'autorisation sollicitée et seront partant examinés dans ce contexte.
1.4. En définitive, le recours en matière de droit public est recevable sous les réserves qui précèdent et le recours constitutionnel subsidiaire est irrecevable.
2.
2.1. Le Tribunal fédéral contrôle librement le respect du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF. Il conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (art. 105 al. 1 LTF), hormis dans les cas prévus à l'art. 105 al. 2 LTF. Selon l'art. 97 al. 1 LTF, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'art. 95 LTF et si la correction du vice est susceptible d'influer sur le sort de la cause (ATF 142 II 355 consid. 6 p. 358; 139 II 373 consid. 1.6 p. 377). La partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées (cf. art. 106 al. 2 LTF). A défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (ATF 137 II 353 consid. 5.1 p. 356). Les faits et les critiques invoqués de manière appellatoire sont irrecevables (cf. ATF 141 IV 369 consid. 6.3 p. 375; 137 II 353 consid. 5.1 p. 356; 133 IV 286 consid. 6.2 p. 288). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal fédéral (art. 99 al. 1 LTF).
2.2. En l'occurrence, les faits présentés au début du mémoire de recours qui ne résultent pas de l'arrêt entrepris ne seront pas pris en considération, dès lors que le recourant ne fait pas valoir, ni ne démontre, que le Tribunal cantonal les aurait arbitrairement ignorés. Par ailleurs, en tant que le recourant dénonce une appréciation arbitraire des faits s'agissant de l'existence de liens affectifs et économiques particulièrement forts avec sa fille, il se contente d'opposer sa propre version des faits à celle retenue par les juges précédents, sans démontrer en quoi cette dernière serait insoutenable. Son grief n'a partant pas à être examiné plus avant. En outre, il ne peut pas être tenu compte des faits allégués postérieurs à l'arrêt querellé et des pièces produites à l'appui du recours, car ces éléments sont nouveaux au sens de l'art. 99 al. 1 LTF.
3.
Le recourant se plaint de la violation de l'art. 8 CEDH. Il estime qu'il doit être autorisé à demeurer en Suisse avec sa fille.
3.1. L'art. 8 CEDH ne confère en principe pas un droit à séjourner dans un Etat déterminé: la Convention ne garantit en effet pas le droit d'une personne d'entrer ou de résider dans un Etat dont elle n'est pas ressortissante ou de n'en être pas expulsée (cf. ATF 144 I 91 consid. 4.2 p. 96 et la jurisprudence de la Cour européenne des droits de l'homme citée; cf. ATF 143 I 21 consid. 5.1 p. 26). Toutefois, le fait de refuser un droit de séjour à un étranger dont la famille se trouve en Suisse peut entraver sa vie familiale et porter ainsi atteinte au droit au respect de la vie privée et familiale garanti par cette disposition. Pour qu'il puisse invoquer la protection de la vie familiale découlant de l'art. 8 CEDH, l'étranger doit entretenir une relation étroite et effective avec une personne de sa famille ayant le droit de résider durablement en Suisse (cf. ATF 141 II 169 consid. 5.2.1 p. 180; 139 I 330 consid. 2.1 p. 335 s.; 137 I 284 consid. 1.3 p. 287). Par ailleurs, il n'y a pas atteinte à la vie familiale si l'on peut attendre des personnes concernées qu'elles réalisent leur vie de famille à l'étranger; l'art. 8 CEDH n'est pas a priori violé si le membre de la famille jouissant d'un droit de présence en Suisse peut quitter ce pays sans difficultés avec l'étranger auquel a été refusée une autorisation de séjour. En revanche, si le départ du membre de la famille pouvant rester en Suisse ne peut d'emblée être exigé sans autres difficultés, il convient de procéder à la pesée des intérêts prévue par l'art. 8 par. 2 CEDH (ATF 144 I 91 consid. 4.2 p. 96).
3.2. En l'occurrence, il résulte de l'arrêt entrepris et il n'est pas contesté que le recourant entretient avec sa fille de nationalité suisse une relation suffisamment étroite pour être protégée par l'art. 8 par. 1 CEDH. Par ailleurs, le départ de la fille du recourant ne saurait être d'emblée exigé, dès lors que celle-ci jouit de la nationalité suisse. Il convient donc de procéder à la pesée des intérêts en présence.
3.3. Une ingérence dans l'exercice du droit garanti par l'art. 8 par. 1 CEDH est possible selon l'art. 8 par. 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale ou à la protection des droits et libertés d'autrui. Cette disposition commande une pesée des intérêts qui suppose de tenir compte de l'ensemble des circonstances et de mettre en balance l'intérêt privé à l'obtention ou au maintien d'un titre de séjour et l'intérêt public à son refus ou à sa révocation (ATF 144 I 91 consid. 4.2 p. 96; 142 II 35 consid. 6.1 p. 47 et les arrêts cités). Pour apprécier ce qui est équitable, il y a lieu de prendre en considération la gravité d'une éventuelle faute commise par l'étranger, la durée de son séjour en Suisse et le préjudice qu'il aurait à subir avec sa famille du fait de l'expulsion, respectivement du refus d'accorder ou de prolonger une autorisation de séjour (ATF 139 I 16 consid. 2.2.1 p. 19).
Dans la pesée des intérêts, il faut aussi tenir compte de l'intérêt fondamental de l'enfant (cf. art. 3 de la Convention du 20 novembre 1989 relative aux droits de l'enfant [CDE; RS 0.107]) à pouvoir grandir en jouissant d'un contact étroit avec ses parents (cf. ATF 144 I 91 consid. 5.2 p. 97 s.; 143 I 21 consid. 5.5.1 p. 29; cf. aussi arrêt de la CourEDH El Ghatet c. Suisse du 8 novembre 2016 [requête n o 56971/10], § 27 s. et 46 s.).
3.4. S'agissant plus particulièrement de demandes de regroupement familial en faveur du parent étranger, la jurisprudence retient ce qui suit.
3.4.1. Lorsque le parent étranger n'a pas l'autorité parentale ni la garde ou lorsqu'il a l'autorité parentale conjointe, mais sans la garde, et ne dispose ainsi que d'un droit de visite sur son enfant habilité à résider en Suisse, il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer ce droit de visite, le parent étranger soit habilité à résider durablement dans le même pays que son enfant (cf. ATF 144 I 91 consid. 5.1 p. 96 s.; 140 I 145 consid. 3.2 p. 147). Sous l'angle du droit à une vie familiale (cf. art. 8 par. 1 CEDH et 13 al. 1 Cst.), il suffit en règle générale que le parent vivant à l'étranger exerce son droit de visite dans le cadre de séjours brefs, au besoin en en aménageant les modalités quant à la fréquence et à la durée ou par le biais de moyens de communication modernes (cf. ATF 144 I 91 consid. 5.1 p. 97). Un droit plus étendu ne peut le cas échéant exister qu'en présence 1) de relations étroites et effectives avec l'enfant d'un point de vue affectif et 2) d'un point de vue économique, 3) de l'impossibilité pratique à maintenir la relation en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent et 4) d'un comportement irréprochable (cf. ATF 144 I 91 consid. 5.2 p. 97 ss et les arrêts cités). Ces exigences doivent être appréciées ensemble et faire l'objet d'une pesée des intérêts globale (ATF 144 I 91 consid. 5.2 p. 97 ss sur chacune des conditions; cf. aussi arrêts 2C_950/2017 du 16 mai 2018 consid. 4.1 et 2C_665/2017 du 9 janvier 2018 consid. 4.2.1 lorsque le parent n'a pas de droit de séjour préalable).
3.4.2. Lorsque le parent étranger a l'autorité parentale et le droit de garde sur son enfant et que cet enfant est de nationalité suisse, les règles sont moins strictes. Ainsi, lors de la pesée des intérêts au sens de l'art. 8 par. 2 CEDH, le fait que le parent étranger qui cherche à obtenir une autorisation de séjour en invoquant ses relations avec un enfant suisse (regroupement familial inversé) a adopté un comportement illégal est à prendre en compte dans les motifs d'intérêt public incitant à refuser l'autorisation requise. Toutefois, seule une atteinte d'une certaine gravité à l'ordre et à la sécurité publics peut l'emporter sur le droit de l'enfant suisse de pouvoir grandir dans sa patrie avec le parent qui a le droit de garde et l'autorité parentale sur lui (cf. ATF 140 I 145 consid. 3.3 p. 148; 137 I 247 consid. 4.2.1 et 4.2.2 p. 250 s.; 136 I 285 consid. 5.2 p. 287; 135 I 153 consid. 2.2 p. 156 ss; 143 consid. 4.4 p. 152 s.). Cette jurisprudence est dictée par le fait que le départ du parent qui a la garde de l'enfant de nationalité suisse entraîne de facto l'obligation pour ce dernier de quitter la Suisse. En pareil cas, le renvoi du parent entre ainsi en conflit avec les droits que l'enfant peut tirer de sa nationalité suisse, comme la liberté d'établissement, l'interdiction du refoulement ou le droit de revenir ultérieurement en Suisse (cf. ATF 140 I 145 consid. 3.3 p. 148; arrêt 2C_606/2013 du 4 avril 2014 consid. 5.3).
3.5. En l'occurrence, la situation a ceci de spécifique que la fille du recourant est, depuis mai 2016, orpheline de mère. Le recourant est seul détenteur de l'autorité parentale, qui ne lui a pas été retirée. A teneur de la décision du 7 juillet 2016, le droit de garde du recourant n'a par ailleurs pas été formellement limité, contrairement à ce que l'arrêt entrepris mentionne (cf. art. 105 al. 2 LTF). L'enfant a toutefois été placée, avec l'accord de son père, chez sa grand-mère maternelle, qui a confirmé vouloir prendre en charge sa petite fille au quotidien (cf. art. 105 al. 2 LTF).
On ne se trouve donc pas dans une situation où l'enfant suisse vivrait avec le parent étranger, de sorte que le refus d'autorisation de séjour entraînerait le départ de Suisse de l'enfant. Toutefois, il se justifie d'appliquer les critères moins restrictifs développés pour ces cas de figure (cf. supra consid. 3.4.2) lorsque, comme en l'espèce, l'autre parent est décédé et l'enfant placé (cf. arrêt 2C_972/2011 du 8 mai 2012 consid 4.2). En effet, contrairement aux procédures de mesures protectrices de l'union conjugale et de divorce, dans lesquelles le soutien financier ainsi que le désir de conserver des relations affectives étroites avec l'enfant résultent en premier lieu de la volonté du parent auquel le juge a accordé un droit de visite, les circonstances d'un placement d'enfant ainsi que l'organisation des relations entre le parent naturel et cet enfant ne dépendent pas en premier lieu de la volonté du parent naturel, mais de celle de l'autorité (cf. arrêt 2C_972/2011 du 8 mai 2012 consid. 4.2). Par ailleurs, selon la jurisprudence de la Cour européenne des droits de l'homme, la prise en charge d'un enfant à des fins d'assistance est une mesure temporaire à suspendre dès que la situation s'y prête et l'Etat doit prendre les mesures propres à réunir les parents et l'enfant concerné (arrêt de la CourEDH, Johansen c. Norvège du 7 août 1996, Recueil CourEDH 1996-III, p. 979 § 78).
Ces particularités liées à la situation des enfants dans les procédures de placement doivent être prises en compte dans la pesée des intérêts de l'art. 8 par. 2 CEDH à effectuer en droit des étrangers. Dans toute la mesure du possible, il s'agit ainsi de prendre des décisions qui ne ferment pas définitivement la porte au but ultime qui consiste à unir à nouveau le parent naturel et l'enfant, en particulier en Suisse lorsque, comme en l'espèce, cet enfant est de nationalité suisse. Partant, seule une atteinte d'une certaine gravité à l'ordre et à la sécurité publics du parent prétendant à une autorisation de séjour peut l'emporter sur le droit de l'enfant suisse faisant l'objet d'une mesure de placement de pouvoir un jour vivre à nouveau avec son parent naturel en Suisse (cf. arrêt 2C_972/2011 du 8 mai 2012 consid. 4.2).
3.6. Sur le vu de ce qui précède et compte tenu de la configuration du cas d'espèce, c'est à tort que le Tribunal cantonal a cité et appliqué les quatre critères applicables aux parents qui n'ont qu'un droit de visite sur leur enfant habilité à résider en Suisse. Il convient au contraire d'appliquer le critère de l'atteinte d'une certaine gravité à l'ordre et la sécurité publics. Cela ne modifie cependant pas le résultat auquel est parvenu le Tribunal cantonal en l'espèce.
3.6.1. Du point de vue de la gravité de l'atteinte à l'ordre public et partant de l'intérêt public à l'éloignement, le recourant, qui n'a jamais séjourné en Suisse légalement, cumule, depuis sa première venue dans ce pays en 1999, les condamnations pénales à des peines privatives de liberté importantes (treize mois en 2003, dix-huit mois en 2011; trois ans en 2013; trente mois en 2016, étant toutefois relevé que la dernière peine comprend la révocation de la libération conditionnelle précédemment octroyée). Chacune de ces peines aurait justifié la révocation d'un titre de séjour si le recourant en avait possédé un (cf. art. 62 al. 1 let. b LEI; ATF 139 I 145 consid. 2.1 p. 147). Ces peines sanctionnent en outre essentiellement des infractions à la loi fédérale sur les stupéfiants, domaine dans lequel il y a lieu de se montrer rigoureux (ATF 139 II 121 consid. 5.3 p. 125 s.; 137 II 297 consid. 3.3 p. 303 s.; arrêt 2C_759/2015 du 10 septembre 2015 consid. 5.1). Il est à relever que le recourant s'est vu reprocher d'avoir participé à des trafics d'héroïne (cf. art. 105 al. 2 LTF). Au vu des peines prononcées, qui reflètent notamment les quantités trafiquées, il est exclu d'envisager que le recourant, lui-même toxicomane, ait agi uniquement pour sa consommation personnelle (sur la prise en compte de ce facteur, cf. arrêts 2C_560/2016 du 6 octobre 2016 consid. 3.3; 2C_625/2007 du 2 avril 2008 consid. 8.4). Les actes commis sont particulièrement graves et le recourant est un multirécidiviste qui refuse de se conformer à l'ordre juridique suisse. La gravité de l'atteinte à l'ordre public est de toute évidence donnée et l'intérêt public à l'éloignement du recourant est important.
3.6.2. Du point de vue de l'intérêt privé, le recourant, qui est venu à l'âge de 17 ans environ en Suisse, n'y a jamais résidé légalement et y a passé de longues périodes en détention ou en institution, ne peut se se prévaloir d'aucune forme d'intégration professionnelle ou sociale à teneur de l'arrêt entrepris. Son intérêt à demeurer en Suisse réside donc uniquement dans les relations qu'il entretient avec sa fille. Sans aller jusqu'à nier la sincérité des sentiments qu'il manifeste à l'égard de celle-ci, on doit relever que son attachement et sa préoccupation sont en partie contredits par son attitude: sa fille était déjà née quand il a commis les infractions qui lui ont valu sa condamnation en 2016 à une peine privative de liberté (d'ensemble) de trente mois. Sa libération est par ailleurs beaucoup trop récente (avril 2018) pour affirmer que le décès de sa compagne l'aurait radicalement changé, alors que le recourant est un multirécidiviste que la paternité n'a pas détourné de la délinquance.
Quant à l'intérêt de l'enfant à grandir auprès de son père, la fille du recourant est désormais orpheline de mère, de sorte que la présence de son père revêt une importance toute particulière. Il convient toutefois de relever que l'enfant a grandi jusqu'à présent essentiellement sans son père, puisqu'il était en traitement ou incarcéré (traitement institutionnel de mai 2013 à février 2015; détention d'octobre 2015 à avril 2018). La petite fille est prise en charge par sa grand-mère maternelle depuis le décès de sa mère en mai 2016 et rien n'indique dans l'arrêt entrepris que cette situation lui serait préjudiciable; au contraire même, puisqu'il résulte du dossier que l'enfant se développe bien compte tenu des circonstances (cf. art. 105 al. 2 LTF). On ne peut donc affirmer que la présence de son père en Suisse est indispensable. Par ailleurs, s'il devait néanmoins être considéré que l'intérêt de l'enfant est mieux préservé en maintenant une relation avec son père, il serait à noter que le refus de l'autorisation sollicitée n'empêchera pas des visites de l'enfant à son père en Albanie, ni les contacts par les moyens de communication modernes.
3.6.3. Il convient enfin de relever que rien dans l'arrêt entrepris n'indique des difficultés de réintégration particulières du recourant dans son pays d'origine, dans lequel il a grandi, dont il parle la langue et où résident plusieurs membres de sa famille.
S'agissant des éventuelles représailles qu'il encourrait de la part d'une famille ennemie de la sienne s'il rentrait dans son pays d'origine (Vendetta), le recourant ne fait pas valoir de modification concrète par rapport à la situation qui prévalait lors de l'examen de sa première demande d'autorisation de séjour. Or, dans le cadre d'une reconsidération, il ne s'agit pas d'examiner librement si les conditions posées à l'octroi d'une autorisation sont réunies, comme cela serait le cas lors d'une première demande d'autorisation, mais uniquement de déterminer si les circonstances se sont modifiées dans une mesure juridiquement pertinente depuis la révocation de l'autorisation, respectivement depuis le refus de son octroi ou de sa prolongation (cf. arrêt 2C_107/2018 du 19 septembre 2018 consid. 3.3). A défaut d'éléments nouveaux, c'est à juste titre que le Tribunal cantonal a renvoyé au jugement du Tribunal administratif du canton de Berne du 15 novembre 2015, dans lequel il a été constaté que le recourant n'avait pas établi de manière concrète le risque de représailles qu'il alléguait. Il ne suffit pas au recourant de se référer dans la présente procédure à des articles de presse ou à des vidéos "youtube" qui concernent d'autres familles que la sienne pour démontrer le contraire.
S'agissant des problèmes de santé, il n'est pas contesté qu'en l'absence d'un défibrillateur automatique implantable (DAI), le recourant risque de faire une syncope grave, voire un arrêt cardiaque fatal. Ces éléments ont largement été examinés et pris en compte lors de la première demande d'autorisation de séjour du recourant (cf. art. 105 al. 2 LTF). Celui-ci a produit comme élément nouveau dans la présente procédure un courrier daté du 20 septembre 2016 d'un cardiologue de Tirana indiquant que le contrôle de l'appareil qu'il porte actuellement ne pourrait pas être effectué en Albanie, car seules d'autres marques sont utilisées. Dans son arrêt, le Tribunal cantonal a retenu que rien n'indiquait que le recourant ne pourrait pas bénéficier de l'implantation d'un dispositif d'une des marques connues en Albanie, avant son départ ou sur place. Le recourant ne démontre pas que ce constat serait arbitraire, de sorte qu'il n'y a pas lieu de s'en écarter (cf. supra consid. 2.1). Il s'ensuit qu'il n'est pas avéré que le recourant ne pourrait pas recevoir les soins nécessaires au traitement de son affection dans son pays d'origine, contrairement à ce qu'il prétend. Au surplus, dans le cadre du contrôle de la proportionnalité du refus de l'autorisation sollicitée, si l'intérêt personnel du recourant à être soigné en Suisse est incontestable, il ne l'emporte pas sur l'intérêt public à l'en éloigner (cf. p. ex. arrêts 2C_899/2017 du 7 juin 2018 consid. 4.3; 2C_972/2011 du 8 mai 2012 consid. 4.3).
3.7. En résumé, la gravité des atteintes à l'ordre public commises par le recourant est telle qu'elle s'oppose à l'octroi d'une autorisation de séjour et son intérêt privé à demeurer auprès de son enfant, de même que l'intérêt de l'enfant à grandir en Suisse avec son père, ne l'emportent pas sur l'intérêt public à l'éloignement de l'intéressé. Le refus d'octroi d'une autorisation de séjour au recourant est proportionné aux circonstances, de sorte que le Tribunal cantonal n'a pas violé l'art. 8 CEDH en rendant l'arrêt attaqué.
4.
Les considérants qui précèdent conduisent au rejet du recours en matière de droit public dans la mesure où il est recevable. La requête de mesure provisionnelle (octroi d'une autorisation de séjour pendant la procédure) est sans objet.
Le recours étant d'emblée dénué de chances de succès, la demande d'assistance judiciaire est rejetée (cf. art. 64 al. 1 LTF). Succombant, le recourant doit supporter les frais judiciaires, qui seront fixés en tenant compte de sa situation financière (cf. art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
La demande d'assistance judiciaire est rejetée.
4.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations, au Département de l'économie et de l'action sociale et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 30 janvier 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber