Ordered priority queues (Q1091146)

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) in O(log n) time. Such a data structure with n elements can be created in O(n log n) time using O(n) storage. A specific implementation based on median split trees is presented. Sequential access of the elements can be done in O(n log log n) time and O(log n) extra storage.