MeCabを用いたSinatraアプリをHerokuにデプロイする方法をご教示ください。

類似の質問がありましたが、回答がありませんでしたので質問させていただきます。

タイトルの通り、MeCabを用いたSinatraアプリをHerokuにデプロイしようとしています。

環境

ローカルPC：Mac OSX

$heroku -v
heroku/7.6.0 darwin-x64 node-v10.6.0 # homebrewで入れました

$ruby -v
ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-darwin16]

$gem list | grep sinatra
sinatra (2.0.3, 2.0.2)

$mecab -v
mecab of 0.996 # homebrewで入れました

herokuのOS:Ubuntu

$heroku run bash
$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.4 LTS"

私のGemfile

source "https://rubygems.org"
gem "sinatra"
gem "sinatra-contrib"
gem "mecab", "0.996"
gem "natto"
gem "pry"

heroku buildpacks

$heroku buildpacks
=== mecab-on-sinatra Buildpack URLs
1. https://github.com/heroku/heroku-buildpack-ruby.git
2. https://github.com/diasks2/heroku-buildpack-mecab.git

エラー

extconf.rb:12:in ``': No such file or directory - mecab-config (Errno::ENOENT)
    from extconf.rb:12:in `<main>'
An error occurred while installing mecab (0.996), and Bundler cannot continue.
Make sure that `gem install mecab -v '0.996'` succeeds before bundling.

   In Gemfile:
     mecab

試したこと

$ heroku run bash

でherokuのbashに入ってgem install mecab -v '0.996'しようとしたところパーミッションがなく、
sudoをつけたらsudoコマンドがnot foundでした…。

どうすればこれらを解決してアプリをデプロイできるでしょうか。ご教示ください。