Aiming to improve the low time performance of A^* algorithm, an algorithm based on Parallel Searching and Fast Inserting (PSFI) was presented. Firstly, well known parallel heuristic search algorithms on shared memory platform were researched. Then the original serial A^* algorithm was improved using a Delayed Single Table Searching (DSTS) method and new data structure. In the next place, a kind of parallel algorithm based on shared memory platform was designed. Finally, the proposed algorithm was implemented with OpenMP. The experimental results on 24-puzzle problem show that the improved serial and parallel algorithms decrease the runtime to 1/140 and 1/450 of the unimproved algorithms respectively. The speed-up ratio of parallel algorithm raises to 3.2 compared with the Parallel Best-NBlock-First (PBNF) algorithm. At the same time, the improved algorithm is strict best-first searching algorithm, which ensures the solution quality and is easy to implement.