Which algorithms are usable for heatmaps and what are their pros and cons
If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device.

Linear interpolation (or rather bilinear interpolation) is simple but requires a square heat sample grid and you get some boundary effects that might be undesirable. The method is the most representative since "empty cells" (i.e., cells without heat information) are simply empty because of sparse sampling and not because they are void of heat. The interpolation tries to fill in the missing heat information in the empty cells by looking at the nearby heat samples.

Cell averaging will give you an equally high response in a cell neighboring the heat sample as in the heat sample cell itself (granted that the average is computed for all cells including the cells containing heat samples). If the average is computed for empty cells only (i.e., for cells with no heat information) then the cells with the heat sample will keep its full signal while adjacent cells will contain an average, which in a sparse sample grid will be 1/8 of the heat sample, resulting in a distribution almost as misleading as only using the original heat samples.

Gaussian blurring with a wide enough kernel is simple and gives a better  representation of the impact of the heat samples than the cell averaging. However, the values in the blurred heat map for the empty cells will only be affected by the heat "spread" from the sample cells. So if the heat map is sparse, there will likely be empty cells on equal distance between two heat cells that do not get any heat information at all.

I hope this helps.