A new library to build heatmaps using android is provided at http://code.google.com/p/mapex/
The library not only provide a heatmap overlay that makes simple adding heatmaps to your projects but also some other nice enhancedments to the current android maps PAI:
Area selection with drag and drop
Zoom and Pan events
Utility methods to work with geospatial data
Clustering (soon)
