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.