This happens on older Rails 4/5 where the postgres gem is not pinned to the right minor release:
In your Gemfile replace:
gem 'pg', "~> 0.20"
bundle update and you'll see something like:
Fetching pg 0.21.0 (was 1.2.2)
Installing pg 0.21.0 (was 1.2.2) with native extensions
Redeploy and you're golden. :-)
The full error you'll see in heroku logs / the build log:
Gem::LoadError: Specified 'postgresql' for database adapter, but the gem is not loaded. Add `gem 'pg'` to your Gemfile (and ensure its version is at the minimum required by ActiveRecord).
/tmp/build_c5727176734aa74f802c91ffc857a267/vendor/bundle/ruby/2.6.0/gems/activerecord-4.2.11/lib/active_record/connection_adapters/connection_specification.rb:177:in `rescue in spec'