Mergeable heap

In computer science, a mergeable heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation.

Definition

A mergeable heap supports the usual heap operations:[1]

  • Make-Heap(), create an empty heap.
  • Insert(H,x), insert an element x into the heap H.
  • Min(H), return the minimum element, or Nil if no such element exists.
  • Extract-Min(H), extract and return the minimum element, or Nil if no such element exists.

And one more that distinguishes it:[1]

  • Merge(H1,H2), combine the elements of H1 and H2 into a single heap.

Trivial implementation

It is straightforward to implement a mergeable heap given a simple heap:

Merge(H1,H2):

  1. x ← Extract-Min(H2)
  2. while x ≠ Nil
    1. Insert(H1, x)
    2. x ← Extract-Min(H2)

This can however be wasteful as each Extract-Min(H) and Insert(H,x) typically have to maintain the heap property.

More efficient implementations

Examples of mergeable heap data structures include:

A more complete list with performance comparisons can be found at Heap (data structure) § Comparison of theoretic bounds for variants.

In most mergeable heap structures, merging is the fundamental operation on which others are based. Insertion is implemented by merging a new single-element heap with the existing heap. Deletion is implemented by merging the children of the deleted node.

gollark: Even if better services *do* exist, people generally don't move to something they don't have stuff/people they know on.
gollark: Generally it requires the existing service to be really bad before people start moving.
gollark: Yes, privacy-focused stuff often lacks features. But even if someone came up with "Facebook but significantly better somehow", network effects mean adoption would be very slow.
gollark: Discord isn't ideal, but at least they seem to have a mostly non-data-harvesting business model and somewhat better privacy policy.
gollark: Pretty much, as long as they are also not exposing data from their friends/contacts to big companies too.

See also

References
  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 505–506. ISBN 0-262-03384-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.