hat sich ergeben: A.- Das Dienstverhältnis der Assistenz- und Oberärzte an den staatlichen Spitälern des Kantons Basel-Stadt wird geregelt durch die regierungsrätliche Verordnung vom 26. Juni 1984 betreffend die Anstellungsbedingungen der As- sistenz- und Oberärzte an staatlichen Spitälern (AAOV). Die- se Verordnung stützt sich nach ihrem Ingress auf § 1 Abs. 3 des Beamtengesetzes vom 25. April 1968 und § 1 Abs. 2 des Lohngesetzes vom 12. November 1970. Letzteres wurde inzwi- schen ersetzt durch das Lohngesetz vom 18. Januar 1995, des- sen § 1 Abs. 3 lautet: "Auf Durchgangspositionen (wie zum Beispiel bei As- sistenz- und Oberärzten und -ärztinnen), Praktika und Volontariate zwecks beruflicher Aus-, Weiter- und Fortbildung sowie auf Berufslehrgänge und Be- rufslehren findet das Lohngesetz keine Anwendung. Soweit für solche Dienstverhältnisse weder Ver- ordnungen noch Reglemente bestehen, erlässt das Personalamt entsprechende Weisungen und regelt die Lohnansätze nach einheitlichen Gesichtspunkten." Gemäss Anhang I AAOV betrug der Jahreslohn (inkl. 13. Monatslohn) für Assistenzärzte zwischen Fr. 73'154.25 und Fr. 120'220.75, für stellvertretende Oberärzte zwischen Fr. 118'927.25 und Fr. 167'329.50 und für Oberärzte zwischen Fr. 122'986.50 und Fr. 187'151.25. Am 15. September 1998 änderte der Regierungsrat des Kantons Basel-Stadt die Verordnung ab. Damit wurde ein neuer Absatz eingefügt, wonach der Lohn entsprechend der für das übrige Staatspersonal geltenden Regelung an die Teuerung an- gepasst wird. Sodann wurde die Lohnskala in Anhang I neu festgesetzt. Der Jahreslohn beträgt nach dieser neuen Fas- sung (inkl. 13. Monatslohn) für Assistenzärzte zwischen Fr. 78'120.-- und Fr. 111'231.--, für stellvertretende Ober- ärzte zwischen Fr. 115'024.-- und Fr. 143'780.-- und für Oberärzte zwischen Fr. 119'817.-- und Fr. 146'175.--. Die Änderung enthält ferner Übergangsbestimmungen, wonach für bisherige Stelleninhaber der frankenmässige Lohnanspruch ge- wahrt bleibt. Sie trat am 1. Januar 1999 in Kraft. B.- Der Verband Basler Assistenz- und Oberärzte/-innen erhob am 26. Oktober 1998 staatsrechtliche Beschwerde mit dem Antrag, die Verordnungsänderung vom 15. September 1998 vollumfänglich aufzuheben. Zudem beantragte er Erteilung der aufschiebenden Wirkung. Er rügt eine Verletzung der Gewal- tenteilung und der Rechtsgleichheit. C.- Das Sanitätsdepartement des Kantons Basel-Stadt be- antragte am 12. November 1998 namens des Regierungsrates, das Gesuch um aufschiebende Wirkung abzuweisen. Mit Verfü- gung des Präsidenten der II. öffentlichrechtlichen Abteilung des Bundesgerichts vom 20. November 1998 wurde das Gesuch abgewiesen. D.- Mit Vernehmlassung vom 15. März 1999 beantragte das Sanitätsdepartement, auf die staatsrechtliche Beschwerde nicht einzutreten, eventualiter sie abzuweisen. E.- In dem vom Bundesgericht gemäss Art. 93 Abs. 1 OG angeordneten zweiten Schriftenwechsel hielten die Parteien an ihrem Standpunkt fest.