theodesp / go-heaps

Reference implementations of heap data structures in Go - treap, skew, leftlist, pairing, fibonacci
MIT License
97 stars 29 forks source link

Add heap.Meld to interface definition #24

Closed erjiaqing closed 6 years ago

erjiaqing commented 6 years ago

Many heaps supports the meld operation in O(log n) or even O(1) time complexity, and some heaps are designed for fast meld operation.

theodesp commented 6 years ago

Hey. is it meld similar to merge? because if it is then we the tricky part is to make it work with all implementations. For example:

LeftList

https://github.com/theodesp/go-heaps/blob/3d2ba661b542234e844ebfa1a4b2a866eedf4aaa/leftlist/leftist_heap.go#L35

Skew

https://github.com/theodesp/go-heaps/blob/3d2ba661b542234e844ebfa1a4b2a866eedf4aaa/skew/skew_heap.go#L18

Pairing

https://github.com/theodesp/go-heaps/blob/3d2ba661b542234e844ebfa1a4b2a866eedf4aaa/pairing/pairing_heap.go#L227

So we have different signatures unless we have a generic node type we can use.

erjiaqing commented 6 years ago

How to merge two heaps is quite tricky, and different heaps use different node structure.

I have read some articles, the meld operation seems to be similar to merge. It seems that after c = meld(a, b), and we should not use the old heap a and b anymore.

So I think the a.Meld(b) operation should do the following things:

  1. If a and b is the same kind (e.g. both of them are LeftList), then merge them as the left list do.
  2. as different kind of heaps are hard to merge in most cases, insert items in heap b to heap a one by one if heap a and heap b are different kind of heaps.

In this case, we do not have to use a generic node type.

Heap a = old heap a + old heap b after merge. and Heap b = empty heap after merge.

theodesp commented 6 years ago

Sounds good

theodesp commented 6 years ago

Meld is added with this commit https://github.com/theodesp/go-heaps/commit/d25b436491812d3dcc2e672ba4336ddc7075149d