Checking Priority Queues
Ulrich Finkler, Kurt Mehlhorn · Max Planck Institute for Plasma Physics · 1999
We describe a checker for priority queues. It supports the full repertoire of priority queue operations (insert, del~~in, find-m&, decrease-p, and del-item). It requires U( 1) amortised time per operation and uses linear additional space (i.e. the same amouut as t.he priority queue). The checker reports an error occuring in operation i before operation i + CN + 1 is completed, where N’ is the number of elements in the queue at the time the error occured and c < 1 is a constant. We show that an on-line checker, i.e., a checker that reports errors immediately, must have running time n(n log n) in the worst case for a sequence of n priority queue operations. This lower bound holds in the comparison model of computation.