Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BinaryHeap constructor performs differently from heapify #639

Open
Indigo2233 opened this issue Jun 29, 2020 · 3 comments · May be fixed by #712
Open

BinaryHeap constructor performs differently from heapify #639

Indigo2233 opened this issue Jun 29, 2020 · 3 comments · May be fixed by #712

Comments

@Indigo2233
Copy link

Indigo2233 commented Jun 29, 2020

I noticed that BinaryHeap like BinaryMinHeap constructs a heap that just insert every element from an array to a empty heap. And the following x and y have the same order:

julia> nums = rand(1:20000, 2000);

julia> x = MutableBinaryMinHeap(nums);

julia> y = BinaryMinHeap(Int.([]));

julia> for i in nums 
           push!(y, i)
       end

However, there is an O(N) heap-building algorithm instead of O(NlogN), and function heapify is an implement. So why not use heapify instead of insert successively?

Sincerely.

@Indigo2233 Indigo2233 changed the title BinaryHeap constructor performs different from heapify BinaryHeap constructor performs differently from heapify Jun 29, 2020
@AliMalik9599
Copy link

Hi @oxinabox @AquaIndigo I am interested in fixing this, but I am relatively new to Julia. Any tips on getting started? Thanks!

@oxinabox
Copy link
Member

I recommend asking on julialang slack or Discourse.
The code change should be fairly straight forward if you are familar with the constructor in question and the heapify function

@zerefwayne
Copy link

@AliMalik9599 Are you still working on this issue?

@rushabh-v rushabh-v linked a pull request Dec 10, 2020 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants