The way heroku approaches this is by deploying the new version while the old version is running and then within a few minutes switch routing from the old version to the new version, and then shutting down the old version.

https://devcenter.heroku.com/articles/preboot