Abstract: The heap structures are gaining remarkable progress in recent years. The researches on skew heap, Fibonacci heep and pairing heap performed by the Turing-award recipient R. E. Tarjan in 1986 and his co-authors have attracted more attention, in which the amortized computational complexity is used as measuring criteria. Many network optimization algorithms have been improved due to these achievements.