Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Heap / Priority Queue

Get the smallest or largest item in O(log n).

time O(n log k)space O(k)

What it is

A binary heap keeps the extreme element on top. For top-k problems a heap of size k gives O(n log k), better than sorting everything when k is small.

When to reach for it

  • K largest or smallest
  • Merge k sorted lists
  • Running median, scheduling
  • Dijkstra

Clues in the problem

  • Repeatedly need the current minimum or maximum
  • Sorting is overkill because only k items matter

Template

import heapq
def top_k(a, k):
h = [] # min-heap of the k largest
for x in a:
heapq.heappush(h, x)
if len(h) > k:
heapq.heappop(h)
return sorted(h, reverse=True)

Practice problems

  • Kth Largest Element
  • Top K Frequent Elements
  • Merge k Sorted Lists
  • Find Median from Data Stream

Common mistakes

  • Using a max-heap when a min-heap of size k is the right tool
  • Python heapq is min-only; negate values for max
  • Heapify is O(n), not O(n log n)