Add a DataStructures module with PriorityQueue and heap functions.

[dcjones]

This is good to go, and everyone seems cool with it. See #2438.

[ViralBShah]

I believe the module name Datastructures will conflict with the existing Datastructures.jl package.

Cc: @lindahua

[ViralBShah]

An alternative name could be Collections.

[ViralBShah]

It would be great if docs can be added before merging this.

[dcjones]

Now that you mention it, I think I prefer Collections to DataStructures. One word is better than two.

I've renamed and documented everything now.

[ViralBShah]

exports.jl still seems to be exporting DataStructures.

[dcjones]

Oops. FIxed now.

[ViralBShah]

Silly - but I guess this should be Collections too.

[dcjones]

Certainly. Fixed now.

[ViralBShah]

Thanks. I am going to leave this open for any other API discussions for a little bit.

[stevengj]

Why not just have this in Base (as opposed to Base.Collections or whatever submodule)?

[dcjones]

There's a larger question of how Base should be organized, but with the addition of the Test and Sort modules we seem to be headed in the direction of not putting everything at top-level, so I'm following that trend.

Also, I expect there to be more in the Collections module eventually.

[lindahua]

At line 126 of collections.jl, index should be declared as Dict{K, Int} instead of Dict. I have experienced this many times: if the field types are not completely specific, you will see huge performance penalty. I sometimes see nearly 100x slow down if such a field is at the critical path.

I think a careful benchmark is needed to ensure that the implementation is optimized.

[ViralBShah]

BTW, API-wise this looks good. I think it should be merged, but would like @StefanKarpinski and @JeffBezanson to look at this as well.

@lindahua Agree that we should benchmark this. That can be done even after this pull request is merged though. It would be great if Base.Test can have some support for performance benchmarking, coming to think of it. More generally, we need a way to track performance regressions.

[JeffBezanson]

Please rebase, then I will merge it.

[dcjones]

Rebased!

[pao]

Priority queue tests do not pass: https://travis-ci.org/JuliaLang/julia/jobs/6747796#L602

Appears to be related to the changes in #2347.

[dcjones]

Thanks. It should be working now.