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

**URL:** <https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425>\
**Category:** New to Julia\
**Tags:** array\
**Created:** [June 23, 2021, 8:54am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425 "2021-06-23T08:54:42Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [June 23, 2021, 8:54am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/1 "2021-06-23T08:54:42Z")

</div>

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.

```julia
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

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

```

Thx

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 23, 2021, 9:44am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/2 "2021-06-23T09:44:30Z")

</div>

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.

> [@Bardo](#):
>
> `('`

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

You want something like this

```julia
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

```

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [June 23, 2021, 9:52am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/3 "2021-06-23T09:52:28Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [June 23, 2021, 10:09am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/4 "2021-06-23T10:09:38Z")

</div>

> [@Bardo](#):
>
> Except for different syntax, that is exactly how I coded it in Matlab.

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

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [June 23, 2021, 11:34am UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/5 "2021-06-23T11:34:28Z")

</div>

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
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](https://www.youtube.com/watch?v=YQs6IC-vgmo).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [June 23, 2021, 4:57pm UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/6 "2021-06-23T16:57:44Z")

</div>

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](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).

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [June 23, 2021, 8:13pm UTC](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/7 "2021-06-23T20:13:42Z")

</div>

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