search

theodesp / go-heaps

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

Fibonacci heap #22

Closed radlinskii closed 6 years ago

radlinskii commented 6 years ago

Small preview:

screenshot 2018-10-09 at 21 00 22

I've implemented the algorithm straght from "Introduction to Algorithm". It's working. I can add some tests in addition to the examples.

There is one problem here tho. My implementations of DecreaseKey and Delete methods need the the reference to certain Node, it's not possible to provide it when the Heap is implementing the Interface interface because the Insert method wants a value of node's key, instead of the pointer to the node.

I would like to see it being merged and maybe a new issue created for implementing the Interface interface.

theodesp commented 6 years ago

DecreaseKey and Delete are not part of the Heap Interface so it's not a big problem. But check my comments

radlinskii commented 6 years ago

So should I get rid of DecreaseKey and Delete and make the Heap implement Interface interface?

Also, what comments should I check?

theodesp commented 6 years ago

Check the review comments: https://github.com/theodesp/go-heaps/pull/22/files

Its ok if you leave the DecreaseKey and Delete as they are I will probably refactor them later.

You just make the Heap implement the Interface. Thanx

radlinskii commented 6 years ago

Ok, I will make it implement the Interface interface. I can't see any of your comments though.

theodesp commented 6 years ago

Ok, I will make it implement the Interface interface. I can't see any of your comments though.

Sorry I forgot to finish the review

theodesp commented 6 years ago

Ta