page 1  (8 pages)
2to next section

Are Fibonacci Heaps Optimal?

Diab Abuaiadh and Jeffrey H. Kingston


In this paper we investigate the inherent complexity of the priority queue
abstract data type. We show that, under reasonable assumptions, there exist sequences of n Insert, n Delete, m DecreaseKey and t FindMin operations, where 1 ? t ? n, which have W(nlogt + n + m) complexity. Although Fibonacci heaps do not achieve this bound, we present a modi?ed Fibonacci heap which does, and so is optimal under our assumptions.

4 January, 1994