Top-K Elements

DSA · Heaps

Theory

Top-k problems ask for the k largest, smallest or most frequent items. Sorting everything takes O(n log n), but keeping a heap of size k takes O(n log k): for the k largest, keep a min-heap of size k and replace its root whenever a bigger item arrives. Bucket sort by frequency can even solve "top k frequent" in O(n).

Why we use it

It avoids sorting the entire dataset when only a few results are needed, which matters for large streams.

When to use it

Use it for leaderboards, trending items, k closest points, top customers and streaming analytics.

How it works

  1. min-heap of size k
  2. For each element x: push x
  3. Heap size > k? Yes: Pop the smallest. No: Continue.
  4. Heap holds the k largest

Syntax

k largest with a size-k min-heap:
for x in data:
    if len(heap) < k: push x
    elif x > heap[0]: replace root with x
Time: O(n log k)   Space: O(k)

Example

def top_k_largest(nums, k):
    best = []                      # kept sorted, size <= k
    for x in nums:
        if len(best) < k:
            best.append(x)
            best.sort()
        elif x > best[0]:
            best[0] = x
            best.sort()
    return sorted(best, reverse=True)

def top_k_frequent(words, k):
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    return sorted(freq, key=lambda w: (-freq[w], w))[:k]

print("Top 3 scores:", top_k_largest([45, 92, 13, 78, 99, 61, 85], 3))
print("Top 2 topics:", top_k_frequent(["sql", "dsa", "sql", "python", "dsa", "sql"], 2))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic