JuliaCollections/DataStructures.jl

BinaryHeap constructor performs differently from heapify

Open

#639 aperta il 29 giu 2020

Vedi su GitHub
 (3 commenti) (2 reazioni) (0 assegnatari)Julia (261 fork)batch import
enhancementgood first issue

Metriche repository

Star
 (738 star)
Metriche merge PR
 (Merge medio 9g 21h) (5 PR mergiate in 30 g)

Descrizione

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.

Guida contributor

Direzione di ricerca
Indaga l'implementazione corrente del costruttore per BinaryMinHeap e MutableBinaryMinHeap nel repository DataStructures.jl. La funzione heapify esiste già ed esegue la costruzione dell'heap in O(N). Il compito è sostituire il ciclo di inserimento sequenziale nel costruttore con una chiamata a heapify. Assicurarsi che il comportamento rimanga identico per tutti i casi, inclusi i casi limite come array vuoti. Controllare eventuali test esistenti e aggiungerne di nuovi per verificare il comportamento ottimizzato.
Tech stack
Nessuno
Dominio
dataperformance
Tipo issue
Funzionalità
DifficoltàQuanto dovrebbe essere impegnativa per un nuovo contributor.
3
Tempo stimatoTempo stimato per completare e verificare uno scope piccolo.
1-3 ore
Stato attivitàQuanto è probabile che la issue sia ancora attiva e reviewable.
Datata
ChiarezzaQuanto chiaramente la issue descrive problema, scope e risultato atteso.
Chiara
Prerequisiti
JuliaBinary heap algorithms
Adatta ai principiantiQuanto la issue è adatta a contributor alla prima esperienza.
70