I have been having this same issue with Heroku deployment now for two days. So much so I have considered just trying to use OpenShift instead, but I am reading Ruby On Rails Tutorial, Second Edition, by Michael Hartl and as you all probably know, they use Heroku. My errors have been deep and involved, so much so I have considered starting over but I feel like I will just end up back at this issue.
As it stands, I read: https://devcenter.heroku.com/articles/sqlite3
If you are starting a new Rails app, you can make postgres the default database by running:
$ rails new -d postgresql
When I do this, this is what I encounter:
$ rails new -d postgresql
Can't initialize a new Rails application within the directory of another, please change to a non-Rails directory first.