# 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:** 1
**Showing post:** 16

<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 21, 2021, 9:16pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/16 "2021-09-21T21:16:28Z")

</div>

Thanks @mschauer for this clarification, strange choice.  
Here is the test code with DataStructures/PriorityQueue:

```julia

using DataStructures

Pqueue() = PriorityQueue{Any, Float16}()

function testm(m, n)
    pq = Pqueue();
    for i = 1:n
        if randn() > 0
            #enqueue!(pq, i + m*rand(), Tuple(rand()));
            enqueue!(pq, Tuple(rand()), i + m*rand());
        else
            #enqueue!(pq, i + m*rand(), (rand(), 2));
            enqueue!(pq, (rand(), 2), i + m*rand());
        end
        if i > m
           d = dequeue!(pq);
        end
    end
    println(m)
end

# run tests varying number of pending events
for m = Int.([5, 5e1, 5e2, 5e3, 5e4])
    @time testm(m, Int(1e6))
end

```

and timing

```julia
5       
  0.970011 seconds (10.47 M allocations: 306.696 MiB, 6.56% gc time)
50
  0.990156 seconds (11.09 M allocations: 314.963 MiB, 5.22% gc time)
500
  1.149040 seconds (12.87 M allocations: 350.281 MiB, 5.04% gc time)
5000
  1.163019 seconds (13.78 M allocations: 355.716 MiB, 5.32% gc time)
50000
  1.340612 seconds (14.23 M allocations: 367.543 MiB, 9.16% gc time)

```

vs. timing of my code above

```julia
5       
  0.298179 seconds (3.51 M allocations: 107.208 MiB, 8.42% gc time, 4.43% compilation time)
50
  0.338175 seconds (3.51 M allocations: 107.003 MiB, 9.77% gc time)
500
  0.319229 seconds (3.50 M allocations: 106.807 MiB, 5.75% gc time)
5000
  0.377245 seconds (3.50 M allocations: 107.121 MiB, 7.56% gc time)
50000
  0.794678 seconds (3.50 M allocations: 109.315 MiB, 3.33% gc time)

```

Interesting. Looks like my sorted list method has (for tcalc = a\*m^b) a lower factor a but a higher exponent b, with a break-even point perhaps at m = 1e6 pending events for the hash-based DataStruct pq.

---

_[View the full topic](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472)._