Not only phone producers, but anyone who creates a version of the Android OS, can specify the maximum allowed heap size, based upon the specific requirements of their devices. Some Android roots, such as CyanogenMod, even allow the user to select the heap size herself as a setting.
You can detect the maximum allowed heap size using the method
Runtime.getRuntime().maxMemory();
Additional information on this topic is available here.
If your app normally needs more than 16MB of heap, a suggested approach would be to set a minimum OS version level in your manifest that ensures that the overwhelming majority of those downloading your app will have at least the amount that you need, and then find a way to degrade your functionality gracefully in a way that reduces your heap requirements as needed, down to a base level of 16MB, for the small number of users with less than your optimal amount of heap who fall through that sieve.
Here are some figures showing the association of phone RAM with OS version (based on current, not original, OS). I believe that a phone having at least 1GB of RAM will almost always have more than 16MB of heap. Note that the percentages here are for the number of phone models supporting the indicated memory, not total phones in use, which may be quite skewed toward certain models. These numbers were obtained by plugging inputs into the following phone finder (which includes 1500 Android phone models) and so are only ballpark figures: http://www.gsmarena.com/search.php3
Percentage of phone models having at least 1GB of RAM, by current OS version (not version at launch):
Phones running Percent of models having at least 1GB of RAM Percentage of all models
4.4 and up 100 percent 1.5
4.3 and up 100 percent 2.9
4.2.x and up 74 percent 18.7
4.1.x and up 71 percent 37
4.0 and up 62 percent 60
2.3.x and up 57 percent 71
2.2 and up 44 percent 93
2.1 and up 44 percent 97
ALL OS VERSIONS: 41.5 percent 100