  One of the biggest open problems in external memory data structures is the
priority queue problem with DecreaseKey operations. If only Insert and
ExtractMin operations need to be supported, one can design a comparison-based
priority queue performing $O((N/B)\lg_{M/B} N)$ I/Os over a sequence of $N$
operations, where $B$ is the disk block size in number of words and $M$ is the
main memory size in number of words. This matches the lower bound for
comparison-based sorting and is hence optimal for comparison-based priority
queues. However, if we also need to support DecreaseKeys, the performance of
the best known priority queue is only $O((N/B) \lg_2 N)$ I/Os. The big open
question is whether a degradation in performance really is necessary. We answer
this question affirmatively by proving a lower bound of $\Omega((N/B) \lg_{\lg
N} B)$ I/Os for processing a sequence of $N$ intermixed Insert, ExtraxtMin and
DecreaseKey operations. Our lower bound is proved in the cell probe model and
thus holds also for non-comparison-based priority queues.
