Fastest data structure for a priority queue

General Usage Performance
21

Is this (just) to have the same interface as in DataStructures.jl? I thought of that.
About the last two sentences I am even less sure. Could you explain?

22

Welcome. As a replacement for

left = searchsortedfirst(pq.times, t)

you can use (same timing in Julia)

    len = length(pq)
    left = 1
    right = len
    while left <= right
        mid = (left + right) >> 1
        if pq[mid][1] > t
            right = mid - 1
        else
            left = mid + 1
        end
    end
    insert!(pq, left, (t, d))
1 Like
23

The python implementation

FYI Rumour says that Python has one of the most efficient dict/hash implementations.

24

That’s partly my motivation for benchmarking it. It’s one of the performant aspects of Python. I’ll definitely report back if I do get around to it.