Thumbnail
Access Restriction
Subscribed

Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Correspondence-based data structures ♦ Double-ended priority queues ♦ Heaps ♦ Leftist trees ♦ Runtime efficiency ♦ Splay trees
Abstract We describe three general methods--total, dual, and leaf correspondence--that may be used to derive efficient double-ended priority queues from single-ended priority queues. These methods are illustrated by developing double-ended priority queues based on the classical heap. Experimental results indicate that the leaf-correspondence method generally leads to a faster double-ended priority queue than either total or dual correspondence. On randomly generated test sets, however, the splay tree outperforms the tested correspondence-based double-ended priority queues.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 5


Open content in new tab

   Open content in new tab
Source: ACM Digital Library