Checking priority queues

Abstract

We describe a checker for priority queues. It supports the full repertoire of priority queue operations (insert, del_min, find_min, decrease_p, and del_item). It requires O(1) amortised time per operation and uses linear additional space (i.e. the same amount as the priority queue). The checker reports all error occurring 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 occurred 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 log n) in the worst case for a sequence of n priority queue operations. This lower bound holds in the comparison model of computation.