# Structs with custom ordering in a heap

**URL:** <https://discourse.julialang.org/t/structs-with-custom-ordering-in-a-heap/28753>\
**Category:** New to Julia\
**Tags:** performance, sort, data\_structures\
**Created:** [September 14, 2019, 4:53am UTC](https://discourse.julialang.org/t/structs-with-custom-ordering-in-a-heap/28753 "2019-09-14T04:53:30Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![milesf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milesf/32/9289_2.png) [@milesf](https://discourse.julialang.org/u/milesf)\
**Post date:** [September 14, 2019, 4:53am UTC](https://discourse.julialang.org/t/structs-with-custom-ordering-in-a-heap/28753/1 "2019-09-14T04:53:30Z")

</div>

I have a collection of structs that I want to maintain with a [heap](https://juliacollections.github.io/DataStructures.jl/latest/heaps/).

The comparison rules for this struct are defined by a custom ordering.

I managed to get sorting working for an array of these structs, but it seems like some code changes are needed to enable feeding a custom ordering into a heap. I’m about to dive into making those changes, but figured it would be wise to check here first too see if those changes are necessary to enable this functionality.

Here’s the array sorting example for reference, in case anyone is trying to accomplish what’s described in the related [Sorting arrays of structures](https://discourse.julialang.org/t/sorting-arrays-of-structures/18725) post, but with multiple fields.

Also welcoming any critiques on improving efficiency of my `Base.lt` function. Two thoughts I had are:

- Is it possible to improve performance if the size of `field_orderings` is known to the compiler? In this snippet, the size should be known, and the loop should be unrolled, but will this still be the case in a more dynamic situation where the orderings array is generated? In my use case, I’m planning on always matching the number of struct fields.
- Is it possible to destructure structs? I’m thinking of something like this:
  - `for {sym,ord} in struct_ordering.field_orderings`.

```julia
struct MyStruct
    a::Int64
    b::Int64
    c::Int64
end

struct FieldOrder
    sym::Symbol
    ord::Base.Ordering
end

struct MyStructOrdering <: Base.Ordering
    field_orderings::AbstractVector{FieldOrder}
end

function Base.lt(struct_ordering::MyStructOrdering, a, b)
    for field_ordering in struct_ordering.field_orderings
        sym = field_ordering.sym
        ord = field_ordering.ord
        va = getproperty(a, sym)
        vb = getproperty(b, sym)
        Base.lt(ord, va, vb) && return true
        Base.lt(ord, vb, va) && return false
    end
    false # a and b are equal
end

mystruct_ordering = MyStructOrdering([
    FieldOrder(:a, Base.Reverse),
    FieldOrder(:b, Base.Forward),
    FieldOrder(:c, Base.Reverse)
    ])

mystructs = collect(MyStruct(rand(-1:1, 3)...) for x=1:9)
    
sorted = sort(mystructs, order=mystruct_ordering)

```

```julia
julia> mystructs
9-element Array{MyStruct,1}:
 MyStruct(-1, 0, 1) 
 MyStruct(-1, 0, 0) 
 MyStruct(0, 1, 1)  
 MyStruct(-1, -1, 1)
 MyStruct(0, -1, 0) 
 MyStruct(0, 1, 0)  
 MyStruct(1, 1, 0)  
 MyStruct(0, 0, 1)  
 MyStruct(-1, 1, 0) 

julia> sorted
9-element Array{MyStruct,1}:
 MyStruct(1, 1, 0)  
 MyStruct(0, -1, 0) 
 MyStruct(0, 0, 1)  
 MyStruct(0, 1, 1)  
 MyStruct(0, 1, 0)  
 MyStruct(-1, -1, 1)
 MyStruct(-1, 0, 1) 
 MyStruct(-1, 0, 0) 
 MyStruct(-1, 1, 0) 

```

---

<div class="post-metadata">

**Author:** ![milesf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milesf/32/9289_2.png) [@milesf](https://discourse.julialang.org/u/milesf)\
**Post date:** [September 14, 2019, 6:20am UTC](https://discourse.julialang.org/t/structs-with-custom-ordering-in-a-heap/28753/2 "2019-09-14T06:20:46Z")

</div>

The [changes to get this working](https://github.com/JuliaCollections/DataStructures.jl/pull/529/commits/0e81395a7a9cba57b4e33c202e0b76ee10412783) were not as involved as I expected. Here’s how this works for heaps now. Note that this depends on the code in my previous post.

Still wondering why I can’t just assign a function to another function with something like: `DataStructures.compare = Base.lt`.

```julia
using DataStructures

#DataStructures.compare = Base.lt # Why won't this shorthand work?
function DataStructures.compare(comp::MyStructOrdering, a, b)
    Base.lt(comp, a, b)
end

# create heap
h = BinaryHeap{MyStruct,MyStructOrdering}(comparer=mystruct_ordering)

# fill heap from previous input array
for s in mystructs push!(h,s) end

# unload heap in sorted order
heapsorted = []
while !isempty(h) push!(heapsorted,pop!(h)) end

# ensure same results as previous sort(array) technique
sorted == heapsorted

```

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [September 14, 2019, 8:04pm UTC](https://discourse.julialang.org/t/structs-with-custom-ordering-in-a-heap/28753/3 "2019-09-14T20:04:21Z")

</div>

I don’t quite know the details of why `DataStructures.compare = Base.lt` doesn’t work, but one important thing to see is that that line is doing something different than

```julia
function DataStructures.compare(comp::MyStructOrdering, a, b)
    Base.lt(comp, a, b)
end

```

In the first case, you are trying to rebind `DataStructures`’s `compare` to point at something new. In the latter case, you are adding a method to the existing `DataStructures.compare` function. And adding methods to existing functions is a key part of how Julia packages interoperate, while on the other hand, rebinding existing functions seems a bit strange.