# Fastest data structure for a priority queue

**URL:** <https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472>\
**Category:** Performance\
**Tags:** data\_structures\
**Created:** [September 20, 2021, 3:25pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472 "2021-09-20T15:25:40Z")\
**Posts on this page:** 4\
**Page:** 2

<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:** [September 24, 2021, 4:58pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/21 "2021-09-24T16:58:33Z")

</div>

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?

---

<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:** [September 24, 2021, 5:01pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/22 "2021-09-24T17:01:19Z")

</div>

Welcome. As a replacement for

> left = searchsortedfirst(pq.times, t)

you can use (same timing in Julia)

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

```

---

<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:** [September 24, 2021, 5:07pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/23 "2021-09-24T17:07:57Z")

</div>

> The python implementation

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

---

<div class="post-metadata">

**Author:** ![carl-aa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carl-aa/32/28089_2.png) [@carl-aa](https://discourse.julialang.org/u/carl-aa)\
**Post date:** [September 24, 2021, 11:20pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/24 "2021-09-24T23:20:34Z")

</div>

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.

[Previous page](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472.md?page=1)