Bipartite binomial heaps

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

  • Amr Elmasry
  • Claus Jensen
  • Jyrki Katajainen

We describe a heap data structure that supports Minimum, Insert, and Borrow at O(1) worst-case cost, Delete at O(lgn) worst-case cost including at most lgn + O(1) element comparisons, and Union at O(lgn) worst-case cost including at most lgn + O(lglgn) 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.

OriginalsprogEngelsk
TidsskriftRAIRO - Theoretical Informatics and Applications
Vol/bind51
Udgave nummer3
Sider (fra-til)121-133
Antal sider13
ISSN0988-3754
DOI
StatusUdgivet - jul. 2017

ID: 188448401