# Create an empty array, then insert (Priority Queue)

Hi,

I want to convert a small Matlab code for a sorted list with key - value pairs (array implementation of a priority queue) to Julia.

Double keys are allowed, but sorted according to addition for causality. Values can be of variable length and type. This seems to rule out PriorityQueue.jl. I also want to compare the speed of Matlab vs. Julia -
I will be happy to report the timings!

So I started naively…
The actual sorting is done in insertion-sort style, so Julia’s insert! appeared close.
The following insert! operations (not so) obviously fail, what’s the correct way?
Please bear with me for the loose syntax below.

``````A = Vector{Float64} #  A = []
insert!(A,1,0.2)        #  A = [0.2]
insert!(A,1,0.1)        #  A = [0.1 0.2]
insert!(A,1,0.1)        #  A = [0.1 0.1 0.2]  # allow double entries
insert!(A,2,0.3)        #  A = [0.1 0.3 0.1 0.2]
``````

and generally, how to do it correctly for

``````A = Vector({Float64, Any)}
insert!(A,1,('toto'))
insert!(A,2,('titi', 1.0)) # allow multi-parameter and -type
``````

Thx

you can have an array of type `Any` for its elements. But unless you use some structure like a linked list your insert operation might be really slow and inefficient since you need to allocate a new array every time.

String in Julia must be wrapped in double quotes `"`. `'` are reserved for characters.

You want something like this

``````mutable struct EgList

array::Vector{Any}

EgList() = new([])

end

function insert!(a::EgList, pos, val)

if pos - length(a.array) == 1

push!(a.array, val)

elseif pos == 1

a.array = vcat([val], a.array)

else

a.array = vcat(a.array[1:pos-1], [val], a.array[pos:end])

end

a

end

A = EgList()

insert!(A,1,0.2)        #  A = [0.2]

insert!(A,1,0.1)        #  A = [0.1 0.2]

insert!(A,1,0.1)        #  A = [0.1 0.1 0.2]  # allow double entries

insert!(A,2,0.3)        #  A = [0.1 0.3 0.1 0.2]

A = EgList()

insert!(A,1,("toto"))

insert!(A,2,("titi", 1.0)) # allow multi-parameter and -type
``````
1 Like

Thx xiaodai!
Except for different syntax, that is exactly how I coded it in Matlab. And no surprise, in Matlab a vector is implemented as (doubly?) linked list. I will look up the equivalent implementation and check the timings.

You be a bit more flexible if you use some other data structure so you can allocate a bigger array before hand or if you know the types of the data, you can avoid the use of `Any`.

For you want to do `EgList` may not be the ideal data structure

You definitely do not need to define your own type to do this. You can use a `Vector{Any}` which can hold any kind of object.

``````julia> A = [] # Vector{Any} by default
Any[]

julia> insert!(A, 1, ("toto",))
1-element Vector{Any}:
("toto",)

julia> insert!(A, 1, ("titi", 1.0))
2-element Vector{Any}:
("titi", 1.0)
("toto",)
``````

The `Vector` data structure is a contiguous one-dimensional array, but you can add and remove items at the front and back, so it works in terms of API for what you want. On modern hardware, a contiguous array is hard to beat and it’s very hard to find a use case where a linked list is better, even for operations that are in principle O(n) for a vector and O(1) for a linked list: Bjarne Stroustrup: Why you should avoid Linked Lists - YouTube.

5 Likes

Oh, btw, since you mentioned priority queues in your title, there is a PriorityQueue data structure in the DataStructures package:

http://juliacollections.github.io/DataStructures.jl/v0.11/priority-queue.html

It requires unique priority keys, however (which is a bit annoying to be honest).

Thx Stefan, apparentl we arrived at asking the same question and the same presentation 