# Binary heap type problems

**URL:** <https://discourse.julialang.org/t/binary-heap-type-problems/54722>\
**Category:** General Usage\
**Created:** [February 6, 2021, 8:35am UTC](https://discourse.julialang.org/t/binary-heap-type-problems/54722 "2021-02-06T08:35:42Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![purplishrock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/purplishrock/32/13451_2.png) [@purplishrock](https://discourse.julialang.org/u/purplishrock)\
**Post date:** [February 6, 2021, 8:35am UTC](https://discourse.julialang.org/t/binary-heap-type-problems/54722/1 "2021-02-06T08:35:42Z")

</div>

(A bit of a long post because error messages)

i’m trying to generate a binary heap (from DataStructures) where the data item is a pair consisting of an integer and a function.

The following works

```julia
julia> function f1() println("hello") end
f1 (generic function with 1 method)

julia> function f2() println("goodbye") end
f2 (generic function with 1 method)

julia> using DataStructures

julia> x = BinaryHeap(Base.By(first), [])
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[])

julia> push!(x, 1=>f1)
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[1 => f1])

julia> push!(x, 2=>f2)
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[1 => f1, 2 => f2])

```

but this doesn’t.

```julia
julia> x = BinaryHeap(Base.By(first), [1=>f1])
BinaryHeap{Pair{Int64,typeof(f1)},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), [1 => f1])

julia> push!(x, 2=>f2)

ERROR: MethodError: Cannot `convert` an object of type typeof(f2) to an object of type typeof(f1)
Closest candidates are:
  convert(::Type{T}, ::T) where T at essentials.jl:171
Stacktrace:
 [1] convert(::Type{Pair{Int64,typeof(f1)}}, ::Pair{Int64,typeof(f2)}) at ./pair.jl:71
 [2] push!(::Array{Pair{Int64,typeof(f1)},1}, ::Pair{Int64,typeof(f2)}) at ./array.jl:934
 [3] heappush!(::Array{Pair{Int64,typeof(f1)},1}, ::Pair{Int64,typeof(f2)}, ::Base.Order.By{typeof(first),Base.Order.ForwardOrdering}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/arrays_as_heaps.jl:72
 [4] push!(::BinaryHeap{Pair{Int64,typeof(f1)},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}, ::Pair{Int64,typeof(f2)}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/binary_heap.jl:91
 [5] top-level scope at REPL[8]:1

```

I’m unclear on why the functions are “typeof(f1)” and “typeof(f2)”. I looked through the documentation because I know the subject of function type annotation has come up before, but I couldn’t find anything which talked about it.

More importantly, if I wanted to explicitly type the array when creating the BinaryHeap structure how would I do that ?

Here’s my attempt.

```julia
julia> x = BinaryHeap(Base.By(first), Array{Pair{Int,Function},1}[])
BinaryHeap{Array{Pair{Int64,Function},1},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Array{Pair{Int64,Function},1}[])

julia> push!(x, 1=>f1)
ERROR: MethodError: Cannot `convert` an object of type Pair{Int64,typeof(f1)} to an object of type Array{Pair{Int64,Function},1}
Closest candidates are:
  convert(::Type{T}, ::AbstractArray) where T<:Array at array.jl:554
  convert(::Type{T}, ::T) where T<:AbstractArray at abstractarray.jl:14
  convert(::Type{T}, ::LinearAlgebra.Factorization) where T<:AbstractArray at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/LinearAlgebra/src/factorization.jl:55
  ...
Stacktrace:
 [1] push!(::Array{Array{Pair{Int64,Function},1},1}, ::Pair{Int64,typeof(f1)}) at ./array.jl:934
 [2] heappush!(::Array{Array{Pair{Int64,Function},1},1}, ::Pair{Int64,typeof(f1)}, ::Base.Order.By{typeof(first),Base.Order.ForwardOrdering}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/arrays_as_heaps.jl:72
 [3] push!(::BinaryHeap{Array{Pair{Int64,Function},1},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}, ::Pair{Int64,typeof(f1)}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/binary_heap.jl:91
 [4] top-level scope at REPL[10]:1

```

I’ve been trying various things, aka guessing, and reading through the docs, can’t seem to locate anything that will help.

Thank you.

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [February 6, 2021, 8:54am UTC](https://discourse.julialang.org/t/binary-heap-type-problems/54722/2 "2021-02-06T08:54:26Z")

</div>

> [@purplishrock](#):
>
> ```julia
> julia> x = BinaryHeap(Base.By(first), Array{Pair{Int,Function},1}[])
> BinaryHeap{Array{Pair{Int64,Function},1},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Array{Pair{Int64,Function},1}[])
> 
> ```

You specified the element type to be a `Array{Pair{Int64,Function},1}`, which is probably not what you intended. Try to use just `Pair{Int,Function}` and see if that works.

> [@purplishrock](#):
>
> I’m unclear on why the functions are “typeof(f1)” and “typeof(f2)

Every function has its own type with supertype `Function`, which allows for dispatch on function type and various optimizations. You can probably imagine that knowing the exact type of a function at compile time helps enormously with inference and optimization of functions that take functions as arguments and use them on some sorts of data.

The problem you ran into is, that you created an array with a single `{Int, Functio}` pair for initialization. The array, upon its creation, tries to take on the most specific type that holds the values you supplied, which happenes to be `{Int,typeof(f1)}`. (This is most often what you want, say, with numbers, but it may seem weird with functions indeed)  
Try creating an array with two different functions initially and see for yourself! Good luck 🙂

Edit: also note, that you can create arrays with explicit type specification by prepending the type to the array literal:

````julia
julia> [1=>(+), 2=>(-)]
2-element Vector{Pair{Int64, Function}}:
 1 => (+)
 2 => (-)

julia> [1=>(+), 2=>(+)]
2-element Vector{Pair{Int64, typeof(+)}}:
 1 => (+)
 2 => (+)

julia> Pair{Int,Function}[1=>(+), 2=>(+)]
2-element Vector{Pair{Int64, Function}}:
 1 => (+)
 2 => (+)
```
````