SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Kth Largest Element (Min-Heap of Size K) Visualizer

Keep a min-heap of the k largest values seen so far. Push each value; if the heap grows past k, pop its smallest. At the end the root is the k-th largest.

Start the Kth Largest Element (Min-Heap of Size K) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n log k)
Average timeO(n log k)
Worst timeO(n log k)
Extra spaceO(k)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Keep at most k = 3 values in a min-heap: the 3 largest so far, smallest on top.
  2. Add 3.
  3. Add 2.
  4. 2 is smaller than its parent, so it bubbles up.
  5. Add 1.
  6. 1 is smaller than its parent, so it bubbles up.
  7. Add 5.
  8. The heap has 4 values, more than 3. Pop the smallest, 1: it cannot be in the top 3.
  9. 5 sinks below the smaller child 2.
  10. The heap holds the 3 largest so far again. Its root 2 is the current k-th largest.
  11. Add 6.
  12. The heap has 4 values, more than 3. Pop the smallest, 2: it cannot be in the top 3.
  13. 6 sinks below the smaller child 3.
  14. The heap holds the 3 largest so far again. Its root 3 is the current k-th largest.
  15. Add 4.
  16. 4 is smaller than its parent, so it bubbles up.
  17. The heap has 4 values, more than 3. Pop the smallest, 3: it cannot be in the top 3.
  18. 6 sinks below the smaller child 4.
  19. The heap holds the 3 largest so far again. Its root 4 is the current k-th largest.
  20. Add 8.
  21. … 4 more steps …
  22. The heap has 4 values, more than 3. Pop the smallest, 5: it cannot be in the top 3.
  23. 7 sinks below the smaller child 6.
  24. The heap holds the 3 largest so far again. Its root 6 is the current k-th largest.
  25. Done. The root, 6, is the 3rd largest value.

Try it with your own input →

Kth largest element (min-heap of size k) in Java, Python, C++, C and JavaScript

int findKthLargest(int[] a, int k) {
  PriorityQueue<Integer> heap = new PriorityQueue<>();
  for (int x : a) {
    heap.add(x);
    if (heap.size() > k) heap.poll();
  }
  return heap.peek();
}
import heapq

def find_kth_largest(a, k):
    heap = []
    for x in a:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]
int findKthLargest(const vector<int>& a, int k) {
  priority_queue<int, vector<int>, greater<int>> heap;
  for (int x : a) {
    heap.push(x);
    if ((int)heap.size() > k) heap.pop();
  }
  return heap.top();
}
#include <stdlib.h>

/* push and pop are the min-heap helpers from "Heap push" and "Heap pop" */
int findKthLargest(int a[], int n, int k) {
  int* heap = malloc((k + 1) * sizeof(int)), size = 0;
  for (int x = 0; x < n; x++) {
    push(heap, &size, a[x]);
    if (size > k) pop(heap, &size);
  }
  int top = heap[0];
  free(heap);
  return top;
}
// push and pop are the min-heap helpers from "Heap push" and "Heap pop"
function findKthLargest(a, k) {
  const heap = [];
  for (const x of a) {
    push(heap, x);
    if (heap.length > k) pop(heap);
  }
  return heap[0];
}

In an interview

LeetCode 215, Kth Largest Element in an Array. Same idea: 703 Kth Largest in a Stream, 347 Top K Frequent.

Quickselect is O(n) on average but O(n²) in the worst case and changes the array; the heap is a steady O(n log k) and also works on a stream. Name both.

More trees