# MeldableHeap: A Randomized Meldable Heap

Learn the meldable heap and its operations.

## We'll cover the following

Here, we describe the `MeldableHeap`

, a priority `Queue`

implementation in which the underlying structure is also a heap-ordered binary tree. However, unlike a `BinaryHeap`

in which the underlying binary tree is completely defined by the number of elements, there are no restrictions on the shape of the binary tree that underlies a `MeldableHeap`

; anything goes.

## Operations in `MeldableHeap`

The `add(x)`

and `remove()`

operations in a `MeldableHeap`

are implemented in terms of the `merge(h1, h2)`

operation. This operation takes two heap nodes `h1`

and `h2`

and merges them, returning a heap node that is the root of a heap that contains all elements in the subtree rooted at `h1`

and all elements in the subtree rooted at `h2`

.

The nice thing about a `merge(h1, h2)`

operation is that it can be defined
recursively. See the below figure:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy