Reflected min-max heaps

✍ Scribed by Christos Makris; Athanasios Tsakalidis; Kostas Tsichlas

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 98 KB
• Volume: 86
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00501-x

✦ Synopsis

In this paper we present a simple and efficient implementation of a min-max priority queue, reflected min-max priority queues. The main merits of our construction are threefold. First, the space utilization of the reflected min-max heaps is much better than the naive solution of putting two heaps back-to-back. Second, the methods applied in this structure can be easily used to transform ordinary priority queues into min-max priority queues. Third, when considering only the setting of min-max priority queues, we support merging in constant worst-case time which is a clear improvement over the best worst-case bounds achieved by Høyer.