Create an empty array, then insert (Priority Queue)


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,2,('titi', 1.0)) # allow multi-parameter and -type


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


   EgList() = new([])


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)


        a.array = vcat(a.array[1:pos-1], [val], a.array[pos: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,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

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

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

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.


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

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 :slight_smile: