Image reconstruction algorithms significantly influence the imaging performance of coded-aperture gamma cameras. However, the widely used Maximum Likelihood Expectation Maximization (MLEM) algorithm falls short in effectively suppressing noise amidst stronger background interference because it relies on the system response matrix under ideal conditions. This paper presents corresponding research and improvements regarding the “pathological” nature of the MLEM algorithm. Firstly, the maximum a posteriori (MAP) algorithm was applied to the image reconstruction of coded aperture imaging, followed by an analysis of the selection methods for key parameters such as the neighborhood size and weight coefficient within the Gibbs prior function of the algorithm. Then, we conducted imaging experiments using the prototype of the coded-aperture gamma camera and compared the image reconstruction results of the MLEM algorithm and the MAP algorithm for the ²²Na point source. In the range of 300 to 1200 iterations, the MLEM reconstructed images exhibited noticeable noise spots, with image quality progressively deteriorating as the iterations deepened. In contrast, the MAP reconstructed images did not present any significant noise spots. The average gradient of the reconstructed images was reduced by 26.45% to 49.16% compared to MLEM, and the contrast-to-noise ratio (CNR) was improved by 42.32% to 351.07%. Furthermore, we compared the reconstruction results of multi-point source images with 3 × 3 and 5 × 5 neighborhood sizes. The results indicate that smaller neighborhood size leads to a decrease in the brightness of the hotspots in the reconstructed images, consistent with the theoretical analysis. Finally, we compared the imaging results of the MLEM and MAP algorithms in two separate scenarios: one with greater distance and the other with stronger interference. In both scenarios, the MAP algorithm demonstrated better signal-to-noise ratio (SNR) performance.