Thumbnail
Access Restriction
Subscribed

Author Sack, J.-R. ♦ Atkinson, M. D. ♦ Santoro, N. ♦ Strothotte, T.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract A simple implementation of double-ended priority queues is presented. The proposed structure, called 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.
Description Affiliation: Univ. Stuttgart, Stuttgart, W. Germany (Strothotte, T.) || Carleton Univ., Ottawa, Ont., Canada (Atkinson, M. D.; Sack, J.-R.; Santoro, N.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 29
Issue Number 10
Page Count 5
Starting Page 996
Ending Page 1000


Open content in new tab

   Open content in new tab
Source: ACM Digital Library