Priority queue in standard library

[stevengj]

It would be good to have a priority queue (e.g. PriorityQueue{K,V}) in the standard library. Maybe based on examples/heap.jl?

[johnmyleswhite]

+1

We had discussed having a DataStructures package (https://groups.google.com/d/msg/julia-dev/k-tRUcg1y1s/0HNQt6R4TpQJ). I think it's badly needed.

[timholy]

On Friday, March 01, 2013 07:00:22 AM John Myles White wrote:

+1

We had discussed having a DataStructures package
(https://groups.google.com/d/msg/julia-dev/k-tRUcg1y1s/0HNQt6R4TpQJ). I
think it's badly needed.

Agreed.

Heap can presumably be implemented much better now using type-tagging, along
the lines of the sorting framework.

--Tim

[stevengj]

The question is, what should go into Julia's standard library and what should go into an external package. The standard library has the advantage of being officially supported, easier to find for users, usable within the standard library itself, and of trustable quality (whereas external packages have extremely variable quality, and this will get worse as the number of packages increases). External packages have the advantages of being easier to update rapidly independent of Julia releases and easier to put experimental functionality into (i.e. the variable quality has its blessings).

A PriorityQueue (or Heap, although I would prefer a name based on the functionality rather than on the choice of implementation algorithm) is so central to many algorithms that I think it belongs in the standard library.

[johnmyleswhite]

All very good points. And I'm certainly not opposed to having the core data structures be in Base.I'd suggest having them in a module inside of Base -- something like Base.DataStructures.

[ViralBShah]

Certainly should be in the standard library.

[toivoh]

It would be nice if we could have the kind of priority queue that allows to update priorities of items in it as well.

[dcjones]

I felt like having a go at this. My implementation is on the dcj/pq branch.

I really like the idiom of a priority queue that behaves like a Dict, mapping keys to priorities, but also provides a dequeue! function that removes and returns the lowest priority element. This makes something like Dijkstra's algorithm pretty trivial to implement.

function dijkstra(A)
    n = size(A)[1]
    path = zeros(Int, n)
    dist = fill(Inf, n)
    dist[1] = 0

    q = PriorityQueue(1:n, dist)
    while !isempty(q)
        u = dequeue!(q)
        for v in 1:n
            if has(q, v) && dist[u] + A[u,v] < q[v]
                dist[v] = q[v] = dist[u] + A[u,v]
                path[v] = u
            end
        end
    end

    return (path, dist)
end

The downside with this approach is that things in the priority queue must be unique, and there is the added overhead of having to maintain a Dict. For that reason, I also added lower level heap functions (heappush!, heappop!, heapify!) that operate and plain arrays and should be very efficient.

[StefanKarpinski]

Nice. heappush! and heappop! should maybe just be push! and pop!, no? cc: @JeffBezanson

[dcjones]

Not in their current incarnation, since they operate on plain arrays (as in heappop!(::AbstractArray)). Making a Heap module and using Heap.pop! is a possibility.

[StefanKarpinski]

Ah, right.

[JeffBezanson]

@dcjones your code looks nice as usual! I made a couple minor updates. We should really consider just dropping this into Base.

[stevengj]

+1 on putting this in Base. I don't see the point of pushing it into a DataStructures subpackage.

[johnmyleswhite]

I have no serious objections to putting this in Base as soon as possible. My only hope is that having something DataStructures will encourage people to add more there.

[dcjones]

@johnmyleswhite I had the same thought, but I'm not entirely sure what else I'd like to see.

One thing I would be excited about, particularly now that we have immutable, are efficient persistent data structures. E.g. immutable PersistentDict and PersistentArray types that could be updated efficiently without copying the whole thing.

[stevengj]

Can this be dropped into Base soon? It doesn't seem like there is any reason for further delay...

[ViralBShah]

@dcjones Could you submit a pull request if this work is ready? I also wonder if @lindahua has a separate implementation in Datastructures.jl.

[lindahua]

Yes, I implemented a mutable binary heap in DataStructures.jl. It would be great if the base has an efficient implementation. That package is meant to provide temporary support for data structures that are not yet in the base.