Heroku + Rails build error: Specified 'postgresql' for database adapter, but the gem is not loaded.

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'

With:
gem 'pg', "~> 0.20"

Then run 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:
rake aborted! 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'