Ordered priority queues

A new data structure called ordered priority queue is introduced in this paper. Elements stored in the data structure have a primary order (key) and a secondary order (priority) associated with them. An ordered min-priority queue allows users to find the minimum priority element in any range (according to key order) inO(logn) time. Such a data structure withn elements can be created inO(n logn) time usingO(n) storage. A specific implementation based on median split trees is presented. Sequential access of the elements can be done inO(n log logn) time andO(logn) extra storage.This work was supported in part by NASA under grant NAG 5-739.