Are Fibonacci Heaps Optimal?

Diab Abuaiadh and Jeffrey H. Kingston

ABSTRACT

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