# Top K Sort

# Top K Sort

Top K sort finds the ( k ) smallest or largest elements and returns them in sorted order. Unlike full sorting, it avoids ordering the entire dataset.

You use it when only the best ( k ) items matter, such as ranking, search results, or recommendation systems.

## Problem

Given an array ( A ) of size ( n ) and integer ( k ), compute:

* the smallest ( k ) elements in sorted order
  or
* the largest ( k ) elements in sorted order

## Algorithm (Min heap for largest k)

To find largest ( k ), maintain a min heap of size ( k ):

1. Insert first ( k ) elements into a min heap
2. For each remaining element:

   * If it is larger than heap minimum, replace it
3. Extract and sort heap

```id="v83k2p"
top_k_largest(A, k):
    heap = min_heap()

    for i in 0..k-1:
        heap.push(A[i])

    for i in k..n-1:
        if A[i] > heap.top():
            heap.pop()
            heap.push(A[i])

    result = []
    while heap not empty:
        result.append(heap.pop())

    reverse(result)
    return result
```

For smallest ( k ), use a max heap instead.

## Example

Let:

( A = [4, 9, 1, 7, 3, 8] ), ( k = 2 )

Largest 2 elements:

( [9, 8] )

Sorted output:

( [8, 9] )

## Correctness

The heap maintains exactly the best ( k ) elements seen so far. Any element worse than the heap boundary cannot belong to the top ( k ), so it is discarded.

## Complexity

| phase      | cost               |
| ---------- | ------------------ |
| build heap | ( O(k) )           |
| scan       | ( O((n-k)\log k) ) |
| output     | ( O(k \log k) )    |

Total:

( O(n \log k) )

Space:

( O(k) )

## Alternative (Quickselect)

1. Partition array around the ( k )-th largest element
2. Sort only the selected ( k ) elements

Cost:

* average ( O(n) ) partition
* ( O(k \log k) ) final sort

## When to Use

Top K sort is appropriate when:

* you need ranked results
* ( k \ll n )
* full sorting would waste time

This pattern appears in search engines, analytics pipelines, and streaming systems where only the highest scoring items are relevant.