We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
BIPARTITE BINOMIAL HEAPS.
- Authors
ELMASRY, AMR; JENSEN, CLAUS; KATAJAINEN, JYRKI
- Abstract
We describe a heap data structure that supports Minimum, Insert, and Borrow at O(1) worst-case cost, Delete at O(lg n) worst-case cost including at most lg n+O(1) element comparisons, and Union at O(lg n) worst-case cost including at most lg n + O(lg lg n) element comparisons, where n denotes the (total) number of elements stored in the data structure(s) prior to the operation. As the resulting data structure consists of two components that are different variants of binomial heaps, we call it a bipartite binomial heap. Compared to its counterpart, a multipartite binomial heap, the new structure is simpler and mergeable, still retaining the efficiency of the other operations.
- Subjects
DATA structures; HEAPS (Mathematics); COMPUTER memory management; NUMBER systems; LOGARITHMS
- Publication
RAIRO - Theoretical Informatics & Applications, 2017, Vol 51, Issue 3, p121
- ISSN
2804-7346
- Publication type
Article
- DOI
10.1051/ita/2017010