JuliaCollections/DataStructures.jl

BinaryHeap constructor performs differently from heapify

オープン

#639 opened on 2020/06/29

 (3 件のコメント) (2 件のリアクション) (0 人の担当者)Julia (261 件のフォーク)batch import
enhancementgood first issue

Repository metrics

Stars
 (745 個のスター)
PR merge metrics
 (平均マージ 1d 18h) (30d で 3 merged PRs)

説明

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.

コントリビューターガイド