A priority queue in which initialization and queue operations takeO(loglogD) time

Many computer algorithms have embedded in them a subalgorithm called a priority queue which produces on demand an element of extreme priority among elements in the queue. Queues on unrestricted priority domains have a running time of (nlogn) for sequences ofn queue operations. We describe a simple priority queue over the priority domain {1,,N} in which initialization, insertion, and deletion takeO(loglogD) time, whereD is the difference between the next lowest and next highest priority elements in the queue. In the case of initialization,D=(N). Finding a least element, greatest element, and the neighbor in priority order of some specified element take constant time. We also consider dynamic space allocation for the data structures used. Space can be allocated in blocks of size (N ^1/p ), for small integerp. This research was supported by the National Science Foundation under grants MCS 77-21092 and MCS 80-002684.