Randomized meldable heap

Last updated November 21, 2019

In computer science, a randomized meldable heap (also Meldable Heap or Randomized Meldable Priority Queue) is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. However, there are no restrictions on the shape of the underlying binary tree.

Heap (data structure) tree-based data structure in computer science

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple, where L and R are binary trees or the empty set and S is a singleton set. Some authors allow the binary tree to be the empty set as well.

This approach has a number of advantages over similar data structures. It offers greater simplicity: all operations for the randomized meldable heap are easy to implement and the constant factors in their complexity bounds are small. There is also no need to preserve balance conditions and no satellite information within the nodes is necessary. Lastly, this structure has good worst-case time efficiency. The execution time of each individual operation is at most logarithmic with high probability.^[1]

Operations

The randomized meldable heap supports a number of common operations. These are insertion, deletion, and a searching operation, findMin. The insertion and deletion operations are implemented in terms of an additional operation specific to the meldable heap, Meld(Q1, Q2).

Meld

The basic goal of the meld (also called merge) operation is to take two heaps (by taking each heaps root nodes), Q1 and Q2, and merges them, returning a single heap node as a result. This heap node is the root node of a heap containing all elements from the two subtrees rooted at Q1 and Q2.

A nice feature of this meld operation is that it can be defined recursively. If either heaps are null, then the merge is taking place with an empty set and the method simply returns the root node of the non-empty heap. If both Q1 and Q2 are not nil, check if Q1 > Q2. If it is, swap the two. It is therefore ensured that Q1 < Q2 and that the root node of the merged heap will contain Q1. We then recursively merge Q2 with Q1.left or Q1.right. This step is where the randomization comes in as this decision of which side to merge with is determined by a coin toss.

function Meld(NodeQ1, NodeQ2)  ifQ1 is nil => returnQ2  ifQ2 is nil => returnQ1  ifQ1 > Q2 => swap Q1 and Q2  if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)  elseQ1.right = Meld(Q1.right, Q2)  return Q1

Insert

With the meld operation complete, inserting into the meldable heap is easy. First, a new node, u, is created containing the value x. This new node is then simply melded with the heaps root node.

function Insert(x)  Node u = new Node  u.x = x  root = Meld(u, root)  root.parent = nil  increment node count

Remove

Similarly easy to the insert operation, Remove() uses the Meld operation to eliminate the root node from the heap. This is done by simply melding the two children of the root node and making the returned node the new root.

function Remove()  root = Meld(root.left, root.right)  if root is not nil => root.parent = nil  decrement node count

FindMin

Possibly the easiest operation for the randomized meldable heap, FindMin() simply returns the element currently stored in the heap's root node.

Additional Operations

Some additional operations that can be implemented for the meldable heap that also have O(logn) worst-case efficiency are:

Remove(u) - Remove the node u and its key from the heap.
Absorb(Q) - Add all elements of the meldable heap Q to this heap, emptying Q in the process.
DecreaseKey(u, y) - Decreases the key in node u to y (pre-condition: y <= u.x).

Efficiency Analysis

As all non-constant-time operations are defined in terms of the Meld operation, the efficiency of these operations can be determined through analysis of the complexity of melding two randomized heaps.

The result of this analysis is that the expected time of any meldable priority queue operation on a n-node randomized heap is O(logn).^[1]^[2]

Operation	Worst-Case Time Efficiency
Meld(Q1, Q2)	O(logn)
Insert(x)	O(logn)
Remove()	O(logn)
FindMin()	O(logn)
Remove(x)	O(logn)
Absorb(Q)	O(logn)

History

The meldable heap appears to have first been proposed in 1998 by Gambin and Malinowski.^[1]

Variants

While the randomized meldable heap is the simplest form of a meldable heap implementation, others do exist. These are:

In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged together. It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations :

A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied:

Related Research Articles

In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: a data structure that stores "items" in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

Binary heap heap data structure that takes the form of a binary tree

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.

In computer science, a pagoda is a priority queue implemented with a variant of a binary tree. The root points to its children, as in a binary tree. Every other node points back to its parent and down to its leftmost or rightmost descendant leaf. The basic operation is merge or meld, which maintains the heap property. An element is inserted by merging it as a singleton. The root is removed by merging its right and left children. Merging is bottom-up, merging the leftmost edge of one with the rightmost edge of the other.

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced by Vuillemin (1980) in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence.

In computer science, a double-ended priority queue (DEPQ) or double-ended heap is a data structure similar to a priority queue or heap, but allows for efficient removal of both the maximum and minimum, according to some ordering on the keys (items) stored in the structure. Every element in a DEPQ has a priority or value. In a DEPQ, it is possible to remove the elements in both ascending as well as descending order.

In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time. Min-max heaps are often represented implicitly in an array; hence it's referred to as an implicit data structure.

In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval of the highest-priority element. Each deletion takes amortized time logarithmic in the number of items that have been in the structure for a longer time than the removed item. Insertions take constant amortized time.

In computer science, a ball tree, balltree or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. The ball tree gets its name from the fact that it partitions data points into a nested set of hyperspheres known as "balls". The resulting data structure has characteristics that make it useful for a number of applications, most notably nearest neighbor search.

A Kinetic Tournament is a kinetic data structure that functions as a priority queue for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner", with the certificates enforcing the winner of each "match" in the tournament. It supports the usual priority queue operations - insert, delete and find-max. They are often used as components of other kinetic data structures, such as kinetic closest pair.

A Kinetic hanger is a randomized version of a kinetic heap whose performance is easy to analyze tightly. A kinetic hanger satisfies the heap property but relaxes the requirement that the tree structure must be strictly balanced, thus insertions and deletions can be randomized. As a result, the structure of the kinetic hanger has the property that it is drawn uniformly at random from the space of all possible heap-like structures on its elements.

In computer science, a mergeable heap is an abstract data type, which is a heap supporting a merge operation.

A weak heap is a combination of the binary heap and binomial heap data structures for implementing priority queues. It can be stored in an array as an implicit binary tree like the former, and has the efficiency guarantees of the latter.

References

1 2 3 A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.
↑ P. Morin, Open Data Structures, p. 191-

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Gambin-1] 1 2 3 A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.

[Morin-2] P. Morin, Open Data Structures, p. 191-