JuliaCollections/DataStructures.jl

BinaryHeap constructor performs differently from heapify

Ouverte

#639 ouverte le 29 juin 2020

Voir sur GitHub
 (3 commentaires) (2 réactions) (0 personne assignée)Julia (261 forks)batch import
enhancementgood first issue

Métriques du dépôt

Stars
 (745 étoiles)
Métriques de merge PR
 (Merge moyen 1j 18h) (3 PRs mergées en 30 j)

Description

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.

Guide contributeur

Direction de recherche
Examinez les constructeurs de BinaryHeap et remplacez l'insertion séquentielle par un appel à heapify pour une construction O(n).
Stack technique
julia
Domaine
backend
Type d'issue
Performance
DifficultéDifficulté estimée pour un nouveau contributeur, de 1 pour un très petit changement à 5 pour un travail expert.
2
Temps estiméFourchette de temps approximative pour investiguer, implémenter, tester et préparer une pull request.
1-3 heures
Statut d'activitéDisponibilité apparente de l'issue : fraîche, active, ancienne, bloquée ou en attente d'un mainteneur.
Active
ClartéClarté avec laquelle l'issue explique le changement attendu, les critères d'acceptation et la prochaine étape.
Claire
Prérequis
JuliaGit
Accessibilité débutantScore de 1 à 100 estimant l'accessibilité de cette issue pour un premier contributeur.
65