# How to return k largest elements of a vector in descending order?

**URL:** <https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559>\
**Category:** New to Julia\
**Tags:** sort, maxima\
**Created:** [October 31, 2022, 12:31pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559 "2022-10-31T12:31:41Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Alex\_ricci](https://avatars.discourse-cdn.com/v4/letter/a/a4c791/32.png) [@Alex\_ricci](https://discourse.julialang.org/u/Alex_ricci)\
**Post date:** [October 31, 2022, 12:31pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/1 "2022-10-31T12:31:41Z")

</div>

Let’s say I have a vector

```julia
a = rand(1:20, 10)
10-element Vector{Int64}:
  2
 13
 10
 12
 10
  8
 10
 14
  1
 19

```

I want to define a function such as f() which takes two inputs including a vector `a` and `k` as the number of largest elements and return the k largest numbers in descending order.  
For example:

```julia
f(a,3) = [19, 14 , 13] 

```

A similar issue is discussed here in 2018, but it looks like some functions like `partialsortperm()` do not work in the newer versions of Julia. I use Julia 1.6.5.

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [October 31, 2022, 12:51pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/2 "2022-10-31T12:51:23Z")

</div>

> [@Alex\_ricci](#):
>
> A similar issue is discussed here in 2018, but it looks like some functions like `partialsortperm()` do not work in the newer versions of Julia. I use Julia 1.6.5.

Not sure what you mean.

```julia
julia> a[partialsortperm(a, 1:3; rev = true)]
3-element Vector{Int64}:
 20
 18
 17

```

works just fine on Julia 1.6.

---

<div class="post-metadata">

**Author:** ![TBuConst](https://avatars.discourse-cdn.com/v4/letter/t/96bed5/32.png) [@TBuConst](https://discourse.julialang.org/u/TBuConst)\
**Post date:** [October 31, 2022, 12:51pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/3 "2022-10-31T12:51:25Z")

</div>

Hi,

does the following function do the trick?

```julia
f(a,k) = sort(a, rev=true)[1:k]

```

Regards,

Thomas

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [October 31, 2022, 1:15pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/4 "2022-10-31T13:15:42Z")

</div>

`partialsortperm` is made for these situations, so you might be leaving quite a bit of performance on the table if you sort the whole vector:

```julia
julia> f1(a, k) = sort(a; rev = true)[1:k];

julia> f2(a, k) = a[partialsortperm(a, 1:k; rev = true)];

julia> using BenchmarkTools

julia> x = rand(1_000_000);

julia> @btime f1($x, 3);
  53.254 ms (3 allocations: 7.63 MiB)

julia> x = rand(1_000_000);

julia> @btime f2($x, 3);
  5.330 ms (5 allocations: 7.63 MiB)

```

an order of magnitude on my machine for 1e6 Float64 elements.

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [October 31, 2022, 1:27pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/5 "2022-10-31T13:27:14Z")

</div>

`partialsort(x, 1:k; rev=true)` is even faster, `perm` is not needed here.

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [October 31, 2022, 7:37pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/6 "2022-10-31T19:37:46Z")

</div>

by @stevengj

> the DataStructures.jl package [already contains such a function](https://juliacollections.github.io/DataStructures.jl/latest/heaps/#Functions-using-heaps-1), implemented using heaps.
> 
> Just call `nlargest(n, array)` from DataStructures.jl

from [this](https://discourse.julialang.org/t/the-quasi-best-maxn-function/52813/6) discussion

---

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [October 31, 2022, 8:02pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/7 "2022-10-31T20:02:08Z")

</div>

To sum it up…

```julia
julia> using DataStructures, BenchmarkTools

julia> f1(a, k) = sort(a; rev = true)[1:k];

julia> f2(a, k) = a[partialsortperm(a, 1:k; rev = true)];

julia> f3(a, k) = partialsort(a, 1:k; rev=true)
f3 (generic function with 1 method)

julia> f4(a, k) = nlargest(k, a)
f4 (generic function with 1 method)

julia> x = rand(1_000_000);

julia> xb = copy(x);

julia> r1 = @btime f1($xb, 3);
  74.432 ms (3 allocations: 7.63 MiB)

julia> xb = copy(x);

julia> r2 = @btime f2($xb, 3);
  13.480 ms (5 allocations: 7.63 MiB)

julia> xb = copy(x);

julia> r3 = @btime f3($xb, 3);
  9.408 ms (2 allocations: 7.63 MiB)

julia> xb = copy(x);

julia> r4 = @btime f4($xb, 3);
  1.531 ms (2 allocations: 160 bytes)

julia> r1 == r2 == r3 == r4
true

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [October 31, 2022, 10:21pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/8 "2022-10-31T22:21:03Z")

</div>

try also this, but for larger arrays

```julia

function MaxN(cr,N)
    maxn = heapify!(cr[1:N])
    maxn1=maxn[1]
       @inbounds for i in N+1:length(cr)
        e=cr[i]    
        if maxn1 < e
            heappop!(maxn)
            heappush!(maxn,e)
            maxn1=maxn[1]
            end
        end
    sort!(maxn,rev=true)
end

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 31, 2022, 10:38pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/9 "2022-10-31T22:38:56Z")

</div>

Why doesn’t `partialsort` use `nlargest` then? What’s the tradeoff?

---

<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:** [November 1, 2022, 12:51am UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/10 "2022-11-01T00:51:19Z")

</div>

Because `nlargest` discards the rest of the array? The two functions aren’t equivalent.

---

<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:** [November 1, 2022, 12:37pm UTC](https://discourse.julialang.org/t/how-to-return-k-largest-elements-of-a-vector-in-descending-order/89559/11 "2022-11-01T12:37:27Z")

</div>

> [@rocco\_sprmnt21](#):
>
> try also this, but for larger arrays

`DataStructures.nlargest` [already uses a heap](https://github.com/JuliaCollections/DataStructures.jl/blob/cb91c86443b43b7d67d0c488ff1dd1accf2083a5/src/heaps.jl#L109-L129) (in a slightly more efficient way because it can combine the push and pop).