Start with heroku. its the easiest and free for trying out.
Once its deployed on heroku, Based on the issues or limitations that you are facing on heroku decide as to whether you need a VPS or shared hosting or any other managed hosting services.
like heroku only has 5mb internal memory na , like my site is based on a user based and a user can upload data, so the space wont be enough na thats why planning to use a vps or a shared web host