# Maintaining a fixed size "top N" values list

**URL:** <https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868>\
**Category:** Performance\
**Created:** [April 1, 2022, 1:35pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868 "2022-04-01T13:35:09Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![taotree](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taotree/32/31982_2.png) [@taotree](https://discourse.julialang.org/u/taotree)\
**Post date:** [April 1, 2022, 1:35pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/1 "2022-04-01T13:35:09Z")

</div>

My high level need: loop through lots of entries and keep track of the top nth value so I can continue filtering out anything lower than the nth highest value.  
My assumption is that I would need to store the n top values. When a higher value comes along, insert it and the lowest value is discarded.  
A naive implementation would be:

```julia
v = zeros(len)
...
if newScore > v[1]
    v[1] = newScore # discard the lowest, add the new
    sort!(v) # move the new lowest into place
end

```

which is obviously going to be very slow for any significant value of `len` (in my case, that is in the thousands).  
I would usually look to a priority queue to handle this situations. I haven’t been able to find a fixed size priority queue in Julia, though. Am I missing something?  
I see the heap and priority queue in DataStructures, but it seems like they are not optimized for my fixed size case where the primary operation is “push and if new, discard min”.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [April 1, 2022, 1:36pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/2 "2022-04-01T13:36:14Z")

</div>

DataStructures.jl has circular buffers or other things that might help.

> **[GitHub - JuliaCollections/DataStructures.jl: Julia implementation of Data...](https://github.com/JuliaCollections/DataStructures.jl)**
>
> Julia implementation of Data structures. Contribute to JuliaCollections/DataStructures.jl development by creating an account on GitHub.

… Sorry, I see you already mentioned that package. But I’d say that it is probably the closest off the shelf tool that you could use.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 1, 2022, 2:02pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/3 "2022-04-01T14:02:23Z")

</div>

> [@taotree](#):
>
> My assumption is that I would need to store the n top values. When a higher value comes along, insert it and the lowest value is discarded.

I think you can use an ordinary heap? For each new value `x`, peek at the smallest element `y` in the heap. If `y < x`, pop `y` and push `x`.

---

<div class="post-metadata">

**Author:** ![piever](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/piever/32/1815_2.png) [@piever](https://discourse.julialang.org/u/piever)\
**Post date:** [April 1, 2022, 2:09pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/4 "2022-04-01T14:09:00Z")

</div>

You could also use a regular vector and keep track of the value _and index_ of the smallest entry in `v`.

For example

```julia
if new_value > min_value
    v[min_index] = new_value # discard the lowest, add the new
    min_value, min_index = findmin(v)
end

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 1, 2022, 2:10pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/5 "2022-04-01T14:10:39Z")

</div>

In fact, the mutable heap provided by DataStructures.jl lets you update the value of the minimum (“top”) value without separate pop/push operations, so it seems perfect for this.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 1, 2022, 2:12pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/6 "2022-04-01T14:12:07Z")

</div>

> [@piever](#):
>
> `min_value, min_index = findmin(v)`

This makes insertion O(n), so you would only want to use it if insertion is rare and/or n is small.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 1, 2022, 4:29pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/7 "2022-04-01T16:29:07Z")

</div>

> [@stevengj](#):
>
> I think you can use an ordinary heap?

I looked into the DataStructures heap code, and it seems that one can implement this more efficiently by calling lower-level heap functions. Basically, you can merge the push/pop operations into a _single_ “percolate” operation, instead of two. It should also be more efficient than the “mutable heap” because it doesn’t maintain an array of indices.

```julia
using DataStructures

struct BoundedBinaryHeap{T, O <: Base.Ordering} <: DataStructures.AbstractHeap{T}
    ordering::O
    valtree::Vector{T}
    n::Int # maximum length

    function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering) where T
        n ≥ 1 || throw(ArgumentError("max heap size $n must be ≥ 1"))
        new{T, typeof(ordering)}(ordering, sizehint!(Vector{T}(), n), n)
    end

    function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering, xs::AbstractVector) where T
        n ≥ length(xs) || throw(ArgumentError("initial array is larger than max heap size $n"))
        valtree = sizehint!(DataStructures.heapify(xs, ordering), n)
        new{T, typeof(ordering)}(ordering, valtree, n)
    end
end

BoundedBinaryHeap(n::Integer, ordering::Base.Ordering, xs::AbstractVector{T}) where T = BoundedBinaryHeap{T}(n, ordering, xs)

BoundedBinaryHeap{T, O}(n::Integer) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O())
BoundedBinaryHeap{T, O}(n::Integer, xs::AbstractVector) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O(), xs)

Base.length(h::BoundedBinaryHeap) = length(h.valtree)
Base.isempty(h::BoundedBinaryHeap) = isempty(h.valtree)
@inline Base.first(h::BoundedBinaryHeap) = h.valtree[1]

Base.pop!(h::BoundedBinaryHeap) = DataStructures.heappop!(h.valtree, h.ordering)

function Base.push!(h::BoundedBinaryHeap, v)
    if length(h) < h.n
        DataStructures.heappush!(h.valtree, v, h.ordering)
    elseif Base.Order.lt(h.ordering, @inbounds(h.valtree[1]), v)
        DataStructures.percolate_down!(h.valtree, 1, v, h.ordering)
    end
    return h
end

```

For example:

```julia
x = randn(10^6);
h = BoundedBinaryHeap{Float64}(10, Base.Order.Forward)
for x in x
    push!(h, x)
end

```

stores the 10 biggest elements of `x` in `h`.

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [April 1, 2022, 7:12pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/8 "2022-04-01T19:12:45Z")

</div>

I’m kinda surprised this isn’t in [https://github.com/joshday/OnlineStats.jl](https://github.com/joshday/OnlineStats.jl) - could make a nice PR.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 1, 2022, 8:10pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/9 "2022-04-01T20:10:01Z")

</div>

> [@taotree](#):
>
> A naive implementation would be:
> 
> ```julia
> v = zeros(len)
> ...
> if newScore > v[1]
> v[1] = newScore # discard the lowest, add the new
> sort!(v) # move the new lowest into place
> end
> 
> ```
> 
> which is obviously going to be very slow for any significant value of `len` (in my case, that is in the thousands).

Not sure that this is so bad of an idea. Especially since you can also amortize the cost of sorting by maintaining a larger buffer, and (partially) sorting it only when it is full. Something like this:

```julia
    v = zeros(2N) # buffer, twice larger than necessary
    i = 1 # i holds the index where we're currently writing in v

    for x in collection
        v[i] = x # always push the new value

        i += 1
        if i > lastindex(v) # only sort when the buffer is full
            partialsort!(v, 1:N) # (and partially sorting the first N elements is enough)
            i = N+1
        end
    end
    partialsort!(v, 1:N) # a last sort to ensure correctness in the end

```

(Of course, this is at the cost of some extra memory)

  

NB: I’m not sure it’s even necessary to fully sort the first N values. Maybe a fast median-like, divide-and-conquer algorithm should be able to only ensure that the Nth element is well placed, and all elements before it are smaller.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [April 1, 2022, 8:11pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/10 "2022-04-01T20:11:22Z")

</div>

I’m pretty sure this is strictly worse than the heap version.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 1, 2022, 8:27pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/11 "2022-04-01T20:27:39Z")

</div>

Not according to my tests (but everything might well depend on the parameters chosen). ~~I don’t know why the heap-based version allocates; if it was avoidable maybe it would compete with the others:~~ [EDIT: _allocations are due to a bug in the benchmark itself; they are avoidable and the heap-based implementation is indeed faster than the others. See below_]

```julia
# plain sort-based implementation
  33.495 ms (1 allocation: 7.94 KiB)

# implementation where the cost if (partial)sort! is amortized
  11.350 ms (1 allocation: 15.75 KiB)

# implementation based on Steven Johnson's modified heap
  54.199 ms (3999492 allocations: 91.55 MiB)

```

> **Full code for the benchmark**
>
> ```julia
> function min_values1(N, collection)
> v = zeros(N)
> @inbounds for x in collection
> if x < last(v)
> v[N] = x
> sort!(v)
> end
> end
> v
> end
> 
> function min_values2(N, collection)
> v = zeros(2N)
> i = 1
> @inbounds for x in collection
> v[i] = x
> 
> i += 1
> if i > lastindex(v)
> partialsort!(v, 1:N)
> i = N+1
> end
> end
> partialsort!(v, 1:N)
> end
> 
> using DataStructures
> 
> struct BoundedBinaryHeap{T, O <: Base.Ordering} <: DataStructures.AbstractHeap{T}
> ordering::O
> valtree::Vector{T}
> n::Int # maximum length
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering) where T
> n ≥ 1 || throw(ArgumentError("max heap size $n must be ≥ 1"))
> new{T, typeof(ordering)}(ordering, sizehint!(Vector{T}(), n), n)
> end
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering, xs::AbstractVector) where T
> n ≥ length(xs) || throw(ArgumentError("initial array is larger than max heap size $n"))
> valtree = sizehint!(DataStructures.heapify(xs, ordering), n)
> new{T, typeof(ordering)}(ordering, valtree, n)
> end
> end
> 
> BoundedBinaryHeap(n::Integer, ordering::Base.Ordering, xs::AbstractVector{T}) where T = BoundedBinaryHeap{T}(n, ordering, xs)
> 
> BoundedBinaryHeap{T, O}(n::Integer) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O())
> BoundedBinaryHeap{T, O}(n::Integer, xs::AbstractVector) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O(), xs)
> 
> Base.length(h::BoundedBinaryHeap) = length(h.valtree)
> Base.isempty(h::BoundedBinaryHeap) = isempty(h.valtree)
> @inline Base.first(h::BoundedBinaryHeap) = h.valtree[1]
> 
> Base.pop!(h::BoundedBinaryHeap) = DataStructures.heappop!(h.valtree, h.ordering)
> 
> function Base.push!(h::BoundedBinaryHeap, v)
> if length(h) < h.n
> DataStructures.heappush!(h.valtree, v, h.ordering)
> elseif Base.Order.lt(h.ordering, @inbounds(h.valtree[1]), v)
> DataStructures.percolate_down!(h.valtree, 1, v, h.ordering)
> end
> return h
> end
> 
> function min_values3(N, collection)
> h = BoundedBinaryHeap{Float64}(N, Base.Order.Reverse)
> @inbounds for x in x
> push!(h, x)
> end
> h
> end
> 
> using BenchmarkTools
> x = randn(1_000_000)
> 
> v1 = min_values1(1000, x);
> @btime min_values1(1000, $x);
> 
> v2 = min_values2(1000, x);
> @assert last(v1) == last(v2)
> @btime min_values2(1000, $x);
> 
> v3 = min_values3(1000, x);
> @assert last(v1) == pop!(v3)
> @btime min_values3(1000, $x);
> 
> ```

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [April 1, 2022, 8:45pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/12 "2022-04-01T20:45:26Z")

</div>

> [@ffevotte](#):
>
> ```julia
> function min_values3(N, collection)
> h = BoundedBinaryHeap{Float64}(N, Base.Order.Reverse)
> @inbounds for x in x
> push!(h, x)
> end
> h
> end
> 
> ```

allocates because you should have `for x in collection` instead (it’s mistakenly reading a global).

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 1, 2022, 8:55pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/13 "2022-04-01T20:55:26Z")

</div>

Ah, my mistake!

So yes, @Oscar_Smith and @stevengj are right and the heap based implementation is faster. Corrected timings:

```julia
# plain sort-based implementation
  34.340 ms (1 allocation: 7.94 KiB)

# implementation where the cost of (partial)sort! is amortized
  11.586 ms (1 allocation: 15.75 KiB)

# implementation based on Steven Johnson's modified heap
  5.114 ms (2 allocations: 7.94 KiB)

```

> **Corrected benchmarking code**
>
> ```julia
> function min_values1(N, collection)
> v = zeros(N)
> @inbounds for x in collection
> if x < last(v)
> v[N] = x
> sort!(v)
> end
> end
> v
> end
> 
> function min_values2(N, collection)
> v = zeros(2N)
> i = 1
> @inbounds for x in collection
> v[i] = x
> 
> i += 1
> if i > lastindex(v)
> partialsort!(v, 1:N)
> i = N+1
> end
> end
> partialsort!(v, 1:N)
> end
> 
> using DataStructures
> 
> struct BoundedBinaryHeap{T, O <: Base.Ordering} <: DataStructures.AbstractHeap{T}
> ordering::O
> valtree::Vector{T}
> n::Int # maximum length
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering) where T
> n ≥ 1 || throw(ArgumentError("max heap size $n must be ≥ 1"))
> new{T, typeof(ordering)}(ordering, sizehint!(Vector{T}(), n), n)
> end
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering, xs::AbstractVector) where T
> n ≥ length(xs) || throw(ArgumentError("initial array is larger than max heap size $n"))
> valtree = sizehint!(DataStructures.heapify(xs, ordering), n)
> new{T, typeof(ordering)}(ordering, valtree, n)
> end
> end
> 
> BoundedBinaryHeap(n::Integer, ordering::Base.Ordering, xs::AbstractVector{T}) where T = BoundedBinaryHeap{T}(n, ordering, xs)
> 
> BoundedBinaryHeap{T, O}(n::Integer) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O())
> BoundedBinaryHeap{T, O}(n::Integer, xs::AbstractVector) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O(), xs)
> 
> Base.length(h::BoundedBinaryHeap) = length(h.valtree)
> Base.isempty(h::BoundedBinaryHeap) = isempty(h.valtree)
> @inline Base.first(h::BoundedBinaryHeap) = h.valtree[1]
> 
> Base.pop!(h::BoundedBinaryHeap) = DataStructures.heappop!(h.valtree, h.ordering)
> 
> function Base.push!(h::BoundedBinaryHeap, v)
> if length(h) < h.n
> DataStructures.heappush!(h.valtree, v, h.ordering)
> elseif Base.Order.lt(h.ordering, @inbounds(h.valtree[1]), v)
> DataStructures.percolate_down!(h.valtree, 1, v, h.ordering)
> end
> return h
> end
> 
> function min_values3(N, collection)
> h = BoundedBinaryHeap{Float64}(N, Base.Order.Reverse)
> @inbounds for x in collection
> push!(h, x)
> end
> h
> end
> 
> using BenchmarkTools
> x = randn(1_000_000)
> 
> v1 = min_values1(1000, x);
> @btime min_values1(1000, $x);
> 
> v2 = min_values2(1000, x);
> @assert last(v1) == last(v2)
> @btime min_values2(1000, $x);
> 
> v3 = min_values3(1000, x);
> @assert last(v1) == pop!(v3)
> @btime min_values3(1000, $x);
> 
> ```

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [April 1, 2022, 10:03pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/14 "2022-04-01T22:03:06Z")

</div>

Let’s just add a bubble-sort-based implementation, which is likely to be fast if most of the first N values are encountered rather early in the data stream:

```julia
function min_values4(N, collection)
    v = fill(Inf, N)
    @inbounds for x in collection
        x < v[N] || continue
        for i in N-1:-1:1
            x < v[i] || break
            (v[i], v[i+1]) = (x, v[i])
        end
    end
    v
end

```

It benchmarks faster than the others on the same dataset:

```julia
# plain sort-based implementation
  34.340 ms (1 allocation: 7.94 KiB)

# implementation where the cost of (partial)sort! is amortized
  11.586 ms (1 allocation: 15.75 KiB)

# implementation based on Steven Johnson's modified heap
  5.114 ms (2 allocations: 7.94 KiB)

# bubble-sort-based implementation
  2.322 ms (1 allocation: 7.94 KiB)

```

> **Benchmarking code**
>
> ```julia
> function min_values1(N, collection)
> v = zeros(N)
> @inbounds for x in collection
> if x < last(v)
> v[N] = x
> sort!(v)
> end
> end
> v
> end
> 
> function min_values2(N, collection)
> v = zeros(2N)
> i = 1
> @inbounds for x in collection
> v[i] = x
> 
> i += 1
> if i > lastindex(v)
> partialsort!(v, 1:N)
> i = N+1
> end
> end
> partialsort!(v, 1:N)
> end
> 
> using DataStructures
> 
> struct BoundedBinaryHeap{T, O <: Base.Ordering} <: DataStructures.AbstractHeap{T}
> ordering::O
> valtree::Vector{T}
> n::Int # maximum length
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering) where T
> n ≥ 1 || throw(ArgumentError("max heap size $n must be ≥ 1"))
> new{T, typeof(ordering)}(ordering, sizehint!(Vector{T}(), n), n)
> end
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering, xs::AbstractVector) where T
> n ≥ length(xs) || throw(ArgumentError("initial array is larger than max heap size $n"))
> valtree = sizehint!(DataStructures.heapify(xs, ordering), n)
> new{T, typeof(ordering)}(ordering, valtree, n)
> end
> end
> 
> BoundedBinaryHeap(n::Integer, ordering::Base.Ordering, xs::AbstractVector{T}) where T = BoundedBinaryHeap{T}(n, ordering, xs)
> 
> BoundedBinaryHeap{T, O}(n::Integer) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O())
> BoundedBinaryHeap{T, O}(n::Integer, xs::AbstractVector) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O(), xs)
> 
> Base.length(h::BoundedBinaryHeap) = length(h.valtree)
> Base.isempty(h::BoundedBinaryHeap) = isempty(h.valtree)
> @inline Base.first(h::BoundedBinaryHeap) = h.valtree[1]
> 
> Base.pop!(h::BoundedBinaryHeap) = DataStructures.heappop!(h.valtree, h.ordering)
> 
> function Base.push!(h::BoundedBinaryHeap, v)
> if length(h) < h.n
> DataStructures.heappush!(h.valtree, v, h.ordering)
> elseif Base.Order.lt(h.ordering, @inbounds(h.valtree[1]), v)
> DataStructures.percolate_down!(h.valtree, 1, v, h.ordering)
> end
> return h
> end
> 
> function min_values3(N, collection)
> h = BoundedBinaryHeap{Float64}(N, Base.Order.Reverse)
> @inbounds for x in collection
> push!(h, x)
> end
> h
> end
> 
> function min_values4(N, collection)
> v = fill(Inf, N)
> @inbounds for x in collection
> x < v[N] || continue
> for i in N-1:-1:1
> x < v[i] || break
> (v[i], v[i+1]) = (x, v[i])
> end
> end
> v
> end
> 
> using BenchmarkTools
> x = randn(1_000_000)
> 
> v1 = min_values1(1000, x);
> @btime min_values1(1000, $x);
> 
> v2 = min_values2(1000, x);
> @assert last(v1) == last(v2)
> @btime min_values2(1000, $x);
> 
> v3 = min_values3(1000, x);
> @assert last(v1) == pop!(v3)
> @btime min_values3(1000, $x);
> 
> v4 = min_values4(1000, x);
> @assert last(v1) == last(v4)
> @btime min_values4(1000, $x);
> 
> ```

---

<div class="post-metadata">

**Author:** ![taotree](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taotree/32/31982_2.png) [@taotree](https://discourse.julialang.org/u/taotree)\
**Post date:** [April 2, 2022, 3:55pm UTC](https://discourse.julialang.org/t/maintaining-a-fixed-size-top-n-values-list/78868/15 "2022-04-02T15:55:50Z")

</div>

Updated: I found a bug in my memmove option and in the previously posted bubble sort option (it needed an initial `v[N] = x` in the loop). I have fixed them here now. Also, I set all fills to Inf because the data includes negative numbers and so zeros would change the test.

After these changes, all the full sorting approaches are very near each other.

```julia
  35.825 ms (0 allocations: 0 bytes)
  638.915 ms (0 allocations: 0 bytes)
  135.472 ms (0 allocations: 0 bytes)
  32.901 ms (0 allocations: 0 bytes)
  125.850 ms (0 allocations: 0 bytes)
  32.692 ms (0 allocations: 0 bytes)

```

And oddly enough, shrinking the dataset back to the original size, the original plain sorting approach appears to be the fastest, but just barely.

```julia
  605.300 μs (0 allocations: 0 bytes)
  9.986 ms (0 allocations: 0 bytes)
  2.600 ms (0 allocations: 0 bytes)
  614.800 μs (0 allocations: 0 bytes)
  2.280 ms (0 allocations: 0 bytes)
  608.400 μs (0 allocations: 0 bytes)

```

---- Original Post ----  
This community is great. Thank you all for so much help. I added two more options: SortedSet and finding the index + memmove (unsafe\_copyto!). I used both searchsortedfirst and looping to find the index, but both resulted in about the same time. I separated out the initialization code from each approach to isolate timing just the usage. I also increased the test size (50m/10k) to match closer what I might be working with.

The bubble sort option still shows as the fastest for me. Curiously, the plain sort approach comes in a close second for me which is different than what you have been seeing, even when changing it back to the smaller data size. Is there some heuristic that got switched perhaps?

```julia
6.469 ms (0 allocations: 0 bytes) # plain sort
70.680 ms (0 allocations: 0 bytes) # partial sort
25.371 ms (0 allocations: 0 bytes) # modified heap
6.458 ms (0 allocations: 0 bytes) # bubble sort
26.923 ms (0 allocations: 0 bytes) # SortedSet
98.929 ms (0 allocations: 0 bytes) # unsafe_copyto!

```

> **Summary**
>
> ```julia
> init1(N) = zeros(N)
> function min_values1(N, collection, v)
> @inbounds for x in collection
> if x < last(v)
> v[N] = x
> sort!(v)
> end
> end
> v
> end
> vr = min_values1(3, [4], [1,3,5])
> # @info "check" vr
> @assert vr == [1,3,4]
> vr = min_values1(3, [6], [1,3,5])
> # @info "check2" vr
> @assert vr == [1,3,5]
> vr = min_values1(3, [1], [1,3,5])
> # @info "check3" vr
> @assert vr == [1,1,3]
> vr = min_values1(3, [0], [1,3,5])
> # @info "check4" vr
> @assert vr == [0,1,3]
> vr = min_values1(3, [2], [1,3,5])
> # @info "check5" vr
> @assert vr == [1,2,3]
> 
> init2(N) = zeros(2N)
> function min_values2(N, collection, v)
> i = 1
> @inbounds for x in collection
> v[i] = x
> 
> i += 1
> if i > lastindex(v)
> partialsort!(v, 1:N)
> i = N+1
> end
> end
> partialsort!(v, 1:N)
> end
> 
> using DataStructures
> 
> struct BoundedBinaryHeap{T, O <: Base.Ordering} <: DataStructures.AbstractHeap{T}
> ordering::O
> valtree::Vector{T}
> n::Int # maximum length
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering) where T
> n ≥ 1 || throw(ArgumentError("max heap size $n must be ≥ 1"))
> new{T, typeof(ordering)}(ordering, sizehint!(Vector{T}(), n), n)
> end
> 
> function BoundedBinaryHeap{T}(n::Integer, ordering::Base.Ordering, xs::AbstractVector) where T
> n ≥ length(xs) || throw(ArgumentError("initial array is larger than max heap size $n"))
> valtree = sizehint!(DataStructures.heapify(xs, ordering), n)
> new{T, typeof(ordering)}(ordering, valtree, n)
> end
> end
> 
> BoundedBinaryHeap(n::Integer, ordering::Base.Ordering, xs::AbstractVector{T}) where T = BoundedBinaryHeap{T}(n, ordering, xs)
> 
> BoundedBinaryHeap{T, O}(n::Integer) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O())
> BoundedBinaryHeap{T, O}(n::Integer, xs::AbstractVector) where {T, O<:Base.Ordering} = BoundedBinaryHeap{T}(n, O(), xs)
> 
> Base.length(h::BoundedBinaryHeap) = length(h.valtree)
> Base.isempty(h::BoundedBinaryHeap) = isempty(h.valtree)
> @inline Base.first(h::BoundedBinaryHeap) = h.valtree[1]
> 
> @inline Base.pop!(h::BoundedBinaryHeap) = DataStructures.heappop!(h.valtree, h.ordering)
> 
> function Base.push!(h::BoundedBinaryHeap, v)
> if length(h) < h.n
> DataStructures.heappush!(h.valtree, v, h.ordering)
> elseif Base.Order.lt(h.ordering, @inbounds(h.valtree[1]), v)
> DataStructures.percolate_down!(h.valtree, 1, v, h.ordering)
> end
> return h
> end
> 
> init3(N) = BoundedBinaryHeap{Float64}(N, Base.Order.Reverse)
> function min_values3(collection, h)
> @inbounds for x in collection
> push!(h, x)
> end
> h
> end
> 
> init4(N) = fill(Inf, N)
> function min_values4(N, collection, v)
> @inbounds for x in collection
> x < v[N] || continue
> v[N] = x
> for i in N-1:-1:1
> x < v[i] || break
> (v[i], v[i+1]) = (x, v[i])
> end
> end
> v
> end
> vr = min_values4(3, [4], [1,3,5])
> # @info "check" vr
> @assert vr == [1,3,4]
> vr = min_values4(3, [6], [1,3,5])
> # @info "check2" vr
> @assert vr == [1,3,5]
> vr = min_values4(3, [1], [1,3,5])
> # @info "check3" vr
> @assert vr == [1,1,3]
> vr = min_values4(3, [0], [1,3,5])
> # @info "check4" vr
> @assert vr == [0,1,3]
> vr = min_values4(3, [2], [1,3,5])
> # @info "check5" vr
> @assert vr == [1,2,3]
> 
> init5(N) = SortedSet{Float64}(Base.Order.ReverseOrdering(), 1000000:(1000000+N-1))
> function min_values5(collection, v)
> @inbounds for x in collection
> if x < first(v)
> delete!(v.bt, DataStructures.beginloc(v.bt)) # pop!(v)
> DataStructures.insert!(v.bt, convert(DataStructures.keytype(v),x), nothing, false) # push!(v, x)
> end
> end
> v
> end
> 
> init6(N) = fill(Inf, N)
> function min_values6(N, collection, v)
> # ptr = pointer(v)
> @inbounds for x in collection
> x < v[N] || continue
> # i = N-1
> # while (i >= 1 && x < v[i])
> # i -= 1
> # end
> # unsafe_copyto!(pointer(v, i+2), pointer(v, i+1), N-i)
> # v[i+1] = x
> 
> i = searchsortedfirst(v, x)
> if i < N
> # unsafe_copyto!(ptr + (i << 3), ptr + ((i-1) << 3), N-i)
> unsafe_copyto!(pointer(v, i+1), pointer(v, i), N-i)
> end
> v[i] = x
> end
> v
> end
> vr = min_values6(3, [4], [1,3,5])
> # @info "check" vr
> @assert vr == [1,3,4]
> vr = min_values6(3, [6], [1,3,5])
> # @info "check2" vr
> @assert vr == [1,3,5]
> vr = min_values6(3, [1], [1,3,5])
> # @info "check3" vr
> @assert vr == [1,1,3]
> vr = min_values6(3, [0], [1,3,5])
> # @info "check4" vr
> @assert vr == [0,1,3]
> vr = min_values6(3, [2], [1,3,5])
> # @info "check5" vr
> @assert vr == [1,2,3]
> 
> using BenchmarkTools
> x = randn(10_000_000)
> N = 1000
> 
> v1 = init1(N)
> v1 = min_values1(N, x, v1);
> v11 = init1(N)
> @btime min_values1($N, $x, $v11);
> 
> v2 = init2(N)
> v2 = min_values2(N, x, v2);
> @assert last(v1) == last(v2)
> v22 = init2(N)
> @btime min_values2($N, $x, $v22);
> 
> v3 = init3(N)
> v3 = min_values3(x, v3);
> @assert last(v1) == pop!(v3)
> v33 = init3(N)
> @btime min_values3($x, $v33);
> 
> v4 = init4(N)
> v4 = min_values4(N, x, v4);
> @assert last(v1) == last(v4)
> v44 = init4(N)
> @btime min_values4($N, $x, $v44);
> 
> v5 = init5(N);
> v5 = min_values5(x, v5);
> # @info "check" first(v1) last(v1) first(v5) last(v5) length(v1) length(v5)
> @assert last(v1) == first(v5);
> v55 = init5(N);
> @btime min_values5($x, $v55);
> 
> v6 = init6(N);
> v6 = min_values6(N, x, v6);
> # @info "check" first(v1) last(v1) first(v6) last(v6) length(v1) length(v6)
> @assert last(v1) == last(v6);
> v66 = init6(N);
> @btime min_values6($N, $x, $v66);
> 
> ```