An efficient construction algorithm for a class of implicit double-ended priority queues
1995 (English)In: Computer journal, ISSN 0010-4620, E-ISSN 1460-2067, Vol. 38, no 10, 818-821 p.Article in journal (Refereed) Published
Priority queues and double-ended priority queues are fundamental data types in Computer Science, and various data structures have been proposed to implement them. In particular, diamond deques, interval heaps, min-max-pair heaps, and twin-heaps provide implicit structures for double-ended priority queues. Although these heap-like structures are essentially the same when they are presented in an abstract manner, they possess different implementations and thus have different construction algorithms. In this paper, we present a fast algorithm for building these data structures. Our results improve over previously fast known algorithms.
Place, publisher, year, edition, pages
1995. Vol. 38, no 10, 818-821 p.
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-8380DOI: 10.1093/comjnl/38.10.818Local ID: 6e365990-e61c-11db-8a98-000ea68e967bOAI: oai:DiVA.org:ltu-8380DiVA: diva2:981272
Godkänd; 1995; 20070408 (ysko)2016-09-292016-09-29Bibliographically approved