About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1999
Conference paper
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.