Julia: Heap data structure containing mutable struct

Question

I am in the process of creating a priority queue for a label setting algorithm applied to a resource constrained shortest path problem.

Initially my thought was to create a simple vector containing my labels (which are defined as a mutable struct), and each time new labels are added to the priority queue, the queue is sorted in order to always choose the next label with the lowest cost. However, the process of sorting the priority queue multiple times is very time consuming.

My mutable struct is defined as:

mutable struct Label
    node::String
    cost::Int64
    time::Float64
end

I am trying to construct a heap data structure containing my labels that keeps track of the label with the lowest cost. I am, however, experiencing tremendous difficulties in making this happen.

I am aware that a Binary Min Max Heap data structure is able to keep track of integers as follows:

h = BinaryMinMaxHeap([4,3,2,1])

Which outputs:

BinaryMinMaxHeap{Int64}([1, 4, 2, 3])

However, I am looking for a way to do this exact thing with a vector containing my aforementioned labels, where the first index of the heap data structure will contain the label with the lowest cost value.

Answer 1

Have a look at the Using alternate orderings section of the DataStructures.jl documentation. One way to achieve what you want is to provide an ordering to the heap:

julia> heap = BinaryHeap(Base.By(l -> l.cost), [Label("1", 2, 0), Label("2", 1, 0), Label("3", 3, 0)])
BinaryHeap{Label, Base.Order.By{var"#5#6", Base.Order.ForwardOrdering}}(Base.Order.By{var"#5#6", Base.Order.ForwardOrdering}(var"#5#6"(), Base.Order.ForwardOrdering()), Label[Label("2", 1, 0.0), Label("1", 2, 0.0), Label("3", 3, 0.0)])

julia> pop!(heap)
Label("2", 1, 0.0)

julia> pop!(heap)
Label("1", 2, 0.0)

julia> pop!(heap)
Label("3", 3, 0.0)

Extending Base.isless for your struct would also work however there are some things to consider. The following would provide the correct result in this test case:

Base.isless(a::Label, b::Label) = a.cost < b.cost

But it is not a correct implementation of this interface. According to the isless documentation:

 •  If isless(x, y) is defined, then so is isless(y, x) and isequal(x, y), and exactly one of those three yields true.

The mutability of your struct can of course cause problems either way since the heap won't sort again just because you've updated a Label, it could be better to have an immutable struct and just delete it and add a new one when you need to update.

If you can forgo mutability, defining Label as a NamedTuple gives you correct implementations of isless and isequal:

Label = @NamedTuple{cost::Int64, time::Float64, node::String}

julia> heap = BinaryMinMaxHeap(Label.([(2, 0.0, "1"), (1, 0.0, "2"), (3, 0.0, "3")]))
BinaryMinMaxHeap{NamedTuple{(:cost, :time, :node), Tuple{Int64, Float64, String}}}(NamedTuple{(:cost, :time, :node), Tuple{Int64, Float64, String}}[(cost = 1, time = 0.0, node = "2"), (cost = 2, time = 0.0, node = "1"), (cost = 3, time = 0.0, node = "3")])

julia> pop!(heap)
(cost = 1, time = 0.0, node = "2")

julia> pop!(heap)
(cost = 2, time = 0.0, node = "1")

julia> pop!(heap)
(cost = 3, time = 0.0, node = "3")