Add build to binary heap #32

Closed

cristaloleg wants to merge 1 commit from master into master

cristaloleg commented

2016-09-04 13:45:11 +00:00

(Migrated from github.com)

This changes allow to build heap from slice in O(n) time.

There was a proposition to add slicer interface(example https://play.golang.org/p/lpOt0Lw_pM) so it will be possible to use construction like:

a := []int{1,2,3,4,5}
heap.Build(a)

Are you okay with this solution?

This changes allow to build heap from slice in O(n) time. There was a proposition to add slicer interface(example https://play.golang.org/p/lpOt0Lw_pM) so it will be possible to use construction like: ``` a := []int{1,2,3,4,5} heap.Build(a) ``` Are you okay with this solution?

emirpasic commented

2016-09-06 16:42:14 +00:00

(Migrated from github.com)

Thanks for contributing. I think having the possibility to build from slice is a great feature for the heap.

I have just two questions:

How about making the the Push function variadic rather than implementing a new function?
Why do we need to call bubbleDownIndex, i.e. why not just call heap.Push invididually which already does the bubbling logic?

Thanks for contributing. I think having the possibility to build from slice is a great feature for the heap. I have just two questions: 1) How about making the the [Push](https://github.com/emirpasic/gods/blob/master/trees/binaryheap/binaryheap.go#L47-L51) function variadic rather than implementing a new function? 2) Why do we need to call [bubbleDownIndex](https://github.com/emirpasic/gods/pull/32/files#diff-dc2de69240ef3089a3fce8099832a3aaR60), i.e. why not just call heap.Push invididually which already does the bubbling logic?

cristaloleg commented

2016-09-06 17:04:30 +00:00

(Migrated from github.com)

Good idea, I will rewrite it.
Suppose you want to build heap from N elements, if you will push N elements into heap this will take O(NlogN) time, executing bubbleDown N/2 times will decrease complexity to O(n) wikipedia

1) Good idea, I will rewrite it. 2) Suppose you want to build heap from N elements, if you will push N elements into heap this will take O(NlogN) time, executing bubbleDown N/2 times will decrease complexity to O(n) [wikipedia](https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap)

emirpasic commented

2016-09-06 18:12:43 +00:00

(Migrated from github.com)