New Progress for Heap Structures——A Discussion on the Role of Amortized Computational Complexity

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.