A pointer-free data structure for merging heaps and min-max heaps

DOI10.1016/0304-3975(91)90262-ZMaRDI QIDQ1177934zbMATH OpenWikidataFDO

Authors Giorgio Gambosi, Enrico Nardelli, Maurizio Talamo

Publication date 26 June 1992

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90262-Z

zbMATH Keywords

heapsmergingpointer-free data structure

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Review text

A data structure is introduced which makes it possible to represent different instances of mergeable priority queues and dequeues within the same array and at the same time. A pointer-free data structure is developed for mergeable heaps and min-max heaps under which the basic operations of Deletemax, Deletemin, Findmax, Findmin, Merge, Newheap and Deleteheap are performed in \(O(1)\) amortized time for each operation and an Insert operation in \(O(\log n)\) time.

Recommendations

• Bounds for min-max heaps
• The relaxed min-max heap: A mergeable double-ended priority queue
• Mergeable double-ended priority queues
• Min-max heaps and generalized priority queues

Cites work

• A data structure for manipulating priority queues
• Amortized Computational Complexity
• An algorithm for merging heaps
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Efficient searching using partial ordering
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding Minimum Spanning Trees
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3956454 (Why is no real title available?)
• scientific article; zbMATH DE number 4062572 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Implicit data structures for fast search and update
• Implicit Data Structures for the Dictionary Problem
• Min-max heaps and generalized priority queues
• On the computational power of pushdown automata
• Partial match retrieval in implicit data structures
• Recursively rotated orders and implicit data structures: A lower bound

Cited in

(7)

• Reflected min-Max heaps
• The relaxed min-max heap: A mergeable double-ended priority queue
• An efficient implicit data structure for relation testing and searching in partially ordered sets
• Probabilistic data structures for priority queues
• The K-D heap: An efficient multi-dimensional priority queue
• Diamond deque: A simple data structure for priority deques
• Range-restricted mergeable priority queues

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: A pointer-free data structure for merging heaps and min-max heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177934)