Carleton University
Technical Report TR-55
July 1984
An Efficient, Implicit Double-Ended Priority Queue
M.D. Atkinson,, Jörg-Rüdiger Sack, Nicola Santoro, T. Strothotte
Abstract
A simple implementation of double-ended priority queues is presented. The proposed structure, calles a min-max heap, can be built in linear time; in contrast to conventional heaps, it allows both FindMin and FindMax to be performed in constant time; Insert, DeleteMin, and DeleteMax operations can be performed in logarithmic time. Min-max heaps can be generalized to support other similar order-statistics operations efficiently (e.g., constant time FindMedian and Logarithmic time DeleteMedian); furthermore, the notion of min-max ordering can be extended to other heap-ordered structures, such as leftist trees.