Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Priority Queue
DSA

Priority Queue

Learn how priority queues efficiently retrieve the highest- or lowest-priority element.

A heap keeps its most extreme element at the top: min-heap → smallest; max-heap → largest.

peek O(1); push/pop O(log n).

Focus on recognizing:

“Kth largest” / “top K” / “always need the smallest so far” → size-k min-heap

Pattern 1: Kth Largest (Size-K Min-Heap)

Kth largest (k=2) over [3,2,1,5,6,4] — the heap never exceeds 2 items; its root is the running answer. Press ▶ to animate.

Kth Largest via Min-Heap

Use a min-heap of size k to find the kth largest element. The heap always holds the k biggest elements seen so far — its root is the answer.

Stream: [3,2,1,5,6,4], k=2. Push each element. When size > k, pop the smallest. Watch the heap grow and shrink as the stream is consumed.

HEAP VISUALIZER
Steps –
ARRAY BACKING
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        heap = min-heap
                      
                        2
                        for num in nums:
                      
                        3
                          heappush(heap, num)
                      
                        4
                          if heap.size > k: heappop(heap)  // drop smallest
                      
                        5
                        return heap.peek()                  // kth largest

Keep only k elements — the root is the kth largest:

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // min

    for (int num : nums) {
        heap.offer(num);

        if (heap.size() > k)
            heap.poll();          // drop smallest
    }

    return heap.peek();
}
import heapq

def find_kth_largest(nums, k):
    heap = []                     # min-heap

    for num in nums:
        heapq.heappush(heap, num)

        if len(heap) > k:
            heapq.heappop(heap)   # drop smallest

    return heap[0]
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap; // min

    for (int num : nums) {
        heap.push(num);

        if ((int)heap.size() > k)
            heap.pop();           // drop smallest
    }

    return heap.top();
}
// JS has no built-in heap — a tiny binary heap covers it
class MinHeap {
  constructor() {
    this.a = [];
  }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;

    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a,
      top = a[0],
      last = a.pop();

    if (a.length) {
      a[0] = last;
      let i = 0;

      for (;;) {
        const l = 2 * i + 1,
          r = l + 1;
        let m = i;

        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;

        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }

    return top;
  }
  get size() {
    return this.a.length;
  }
  get top() {
    return this.a[0];
  }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();

  for (const num of nums) {
    heap.push(num);

    if (heap.size > k) heap.pop(); // drop smallest
  }

  return heap.top;
}

Min-heap of size k tracks the k biggest seen. Root = kth largest. Memory O(k), not O(n).

Pattern 2: Top K Frequent Elements

A size-k min-heap sacrifices its weakest member on every overflow.

Top K Frequent Elements

Find the k most frequent elements. Count frequencies, then use a min-heap of size k — the root is always the weakest survivor. Evict on overflow.

Frequencies: 1→3, 2→2, 3→1. Heap capped at k=2. Watch the heap grow and evict as frequencies are processed.

HEAP VISUALIZER
Steps –
ARRAY BACKING
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        freq = count every value
                      
                        2
                        heap = []
                      
                        3
                        for (value, f) in freq:
                      
                        4
                          push (f, value)
                      
                        5
                          if size > k: pop smallest
                      
                        6
                        answer = heap contents

Count, then heap on frequency:

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums)
        count.merge(n, 1, Integer::sum);

    PriorityQueue<int[]> heap =
        new PriorityQueue<>((a, b) -> a[1] - b[1]); // by freq

    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});

        if (heap.size() > k)
            heap.poll();
    }

    return heap.stream().mapToInt(a -> a[0]).toArray();
}
from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)

    return [num for num, _ in
            heapq.nlargest(k, count.items(),
                           key=lambda kv: kv[1])]
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;

    auto cmp = [&count](int a, int b) {
        return count[a] > count[b];   // min-heap by freq
    };
    priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);

    for (auto& [num, _] : count) {
        heap.push(num);

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

    vector<int> result;
    while (!heap.empty()) {
        result.push_back(heap.top());
        heap.pop();
    }
    return result;
}
function topKFrequent(nums, k) {
  const count = new Map();
  for (const n of nums)
    count.set(n, (count.get(n) ?? 0) + 1);

  // bucket sort beats a heap here: freq ≤ n
  const buckets = Array.from(
    { length: nums.length + 1 },
    () => [],
  );
  for (const [num, freq] of count) buckets[freq].push(num);

  const result = [];
  for (let f = buckets.length - 1; f >= 0 && result.length < k; f--)
    result.push(...buckets[f]);

  return result;
}

Size-(k−n) trick: min-heap keeps the k highest frequencies; bucket sort is O(n) when frequencies are bounded.

Pattern 3: Dijkstra’s Shortest Path

Pop the closest unsettled node; greedy order guarantees correctness with weights.

Dijkstra (Priority Queue)

Shortest paths from a source using a min-heap of (distance, node).

The min-heap orders nodes by true distance; pop the smallest unsettled node, settle it, then relax its edges (push updated distances). A min-priority queue makes 'always pick the closest unsettled node' efficient. Correct only with non-negative weights.

GRAPH VISUALIZER
Steps –
1421ABCD
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        heap = [(0, start)]
                      
                        2
                        while heap:
                      
                        3
                          (d, n) = pop min; if settled skip
                      
                        4
                          settle n with distance d
                      
                        5
                          relax edges: push (d+w, nb)

Min-heap ordered by distance:

public int[] dijkstra(List<List<int[]>> graph, int src) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    PriorityQueue<int[]> heap =
        new PriorityQueue<>((a, b) -> a[1] - b[1]); // [node,d]
    heap.offer(new int[]{src, 0});

    while (!heap.isEmpty()) {
        int[] cur = heap.poll();

        if (cur[1] > dist[cur[0]]) continue;  // stale entry

        for (int[] edge : graph.get(cur[0])) {
            int next = edge[0], weight = edge[1];

            if (dist[next] > cur[1] + weight) {
                dist[next] = cur[1] + weight;
                heap.offer(new int[]{next, dist[next]});
            }
        }
    }

    return dist;
}
import heapq

def dijkstra(graph, src):
    dist = {src: 0}
    heap = [(0, src)]

    while heap:
        d, node = heapq.heappop(heap)

        if d > dist.get(node, float("inf")):
            continue              # stale entry

        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))

    return dist
vector<long long> dijkstra(vector<vector<pair<int,int>>>& graph,
                           int src) {
    int n = graph.size();
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;

    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> heap;         // min by distance
    heap.push({0, src});

    while (!heap.empty()) {
        auto [d, node] = heap.top();
        heap.pop();

        if (d > dist[node]) continue;   // stale entry

        for (auto& [next, w] : graph[node])
            if (dist[next] > d + w) {
                dist[next] = d + w;
                heap.push({dist[next], next});
            }
    }

    return dist;
}
function dijkstra(graph, src) {
  // graph: adjacency list [next, weight][]
  const dist = new Array(graph.length).fill(Infinity);
  dist[src] = 0;

  const heap = [[0, src]]; // min-first via sort insert (small inputs)

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, node] = heap.shift();

    if (d > dist[node]) continue; // stale entry

    for (const [next, w] of graph[node]) {
      if (dist[next] > d + w) {
        dist[next] = d + w;
        heap.push([dist[next], next]);
      }
    }
  }

  return dist;
}

The stale-entry check (if d > dist[node]: skip) replaces decrease-key in lazy heaps.

Common Mistakes

Using a max-heap for kth largest.

You’d keep ALL n elements. A size-k MIN-heap holds the k biggest — root is the answer.

Forgetting the stale check in Dijkstra.

Without if d > dist[node], old entries re-expand nodes — correctness still holds but time degrades badly on dense graphs.

Comparing heap items without a key function.

Java needs a comparator, C++ needs greater<> or custom cmp — the default orders by first generic argument only.

Complexity

OperationTime
push / popO(log n)
peekO(1)
kth largest (size-k heap)O(n log k)
DijkstraO((V + E) log V)

My Private Notes

Notes are auto-saved locally to this device.