DataStructures.jl icon indicating copy to clipboard operation
DataStructures.jl copied to clipboard

Optimisation: Use heapify in MutableBinaryHeap

Open rushabh-v opened this issue 3 years ago • 6 comments

Fixes: https://github.com/JuliaCollections/DataStructures.jl/issues/639

Note: I was a little confused by the issue-description, so not sure if the changes I made are at the correct place.

rushabh-v avatar Dec 10 '20 17:12 rushabh-v

@AquaIndigo can you review?

oxinabox avatar Dec 10 '20 19:12 oxinabox

CI fails so i suspect this is not correct

oxinabox avatar Dec 10 '20 19:12 oxinabox

Turned out I haven't updated nodemap after calling heapify. I am wondering if we can do that efficiently (without using extra space).

Or does the issue intend to use heapify at some other place @AquaIndigo? (That was the confusion that I mentioned here)

rushabh-v avatar Dec 10 '20 19:12 rushabh-v

Turned out I haven't updated nodemap after calling heapify. I am wondering if we can do that efficiently (without using extra space).

Or does the issue intend to use heapify at some other place @AquaIndigo? (That was the confusion that I mentioned here)

I think that heapify! could help.

Indigo2233 avatar Dec 10 '20 23:12 Indigo2233

I ran the tests locally, it was all green.

rushabh-v avatar Dec 11 '20 13:12 rushabh-v

Sorry for taking so long to review this. I lost track of it

It may also need rebasing to get out new CI setup to work

oxinabox avatar Dec 29 '20 17:12 oxinabox