A heap data structure supporting a meld operation that combines two heaps into one while preserving the heap order. The cost of melding distinguishes implementations such as a leftist heap from ordinary binary heaps.
A meldable heap satisfying the min-heap ordering: each parent key is no greater than its children's keys. It combines efficient merging with access to the current minimum key.
A binary meldable heap satisfying heap order and the leftist condition: at each node, the shortest path to a missing child is no longer in the right subtree than in the left. Melding recurses down right spines, swaps children when needed, and takes logarithmic time.
Articles by others on the same topic
There are currently no matching articles.