Patterns

Maintain a heap of size k while scanning items

When to useK largest, K closest, top K frequent

iterative

INITIALIZE

min-heap (or max-heap depending on direction)

const heap = new MinHeap((a, b) => b[0] - a[0]);

const distance = (p) => (you[0] - p[0]) ** 2 + (you[1] - p[1]) ** 2;
const heap = new MinHeap((a, b) => b[0] - a[0]);

const heap = new MinHeap();

—

TRAVERSE

for-of items

for (const pt of points) {

for (const p of postOffices) {

for (const num of nums) {

—

push

heap.push(item)

  heap.push([pt[0] ** 2 + pt[1] ** 2, pt]);

  heap.push([distance(p), p]);

  heap.push(num);

—

[EVICT]

if heap size > k, pop smallest

  if (heap.size() > k) heap.pop();

  if (heap.size() > k) heap.pop();

  if (heap.size() > k) heap.pop();

—

RETURN

heap contents = the top k

const res = [];
while (heap.size() > 0) res.push(heap.pop());
res.sort((a, b) => a[0] - b[0]);
return res.map(([, pt]) => pt);

const result = [];
while (heap.size() > 0) result.push(heap.pop());
result.sort((a, b) => a[0] - b[0]);
return result.map(([, pt]) => pt);

return heap.peek();

—