Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
15

DSA · Lesson 15 of 20 · 4 min

Heaps and Priority Queues

You'll use this to solve any "top K" or "most frequent" problem, and to explain how to build an efficient task scheduler.

A heap is your go-to structure when you need quick access to the largest or smallest item in a dynamic collection. If an interview question involves finding the "top K items," "Kth largest element," or processing tasks by priority, a heap is almost always the intended solution.

It beats a sorted array because insertions are O(log N) instead of O(N). It beats an unsorted array because finding the min/max is O(1) instead of O(N). This trade-off is the entire point.

How a Heap Works: The Array-as-Tree Trick

A heap is a binary tree with two rules. First, it must be a "complete" tree, meaning all levels are full except possibly the last, which is filled left-to-right. This structure lets you store the tree in an array without pointers.

Second, it must obey the heap property. In a min-heap, every parent node is smaller than or equal to its children. This guarantees the smallest element is always at the root. A max-heap is the opposite.

For a zero-indexed array arr, the mapping is simple:

  • A node at index i has children at 2*i + 1 and 2*i + 2.
  • A node at index i has its parent at Math.floor((i - 1) / 2).

The trap: Candidates sometimes mix up the formulas for 0-indexed and 1-indexed arrays. In an interview, state that you're using a 0-indexed array and stick to these formulas.

Implementing the Core Operations

The two key operations are insert and extractMin (or extractMax). Everything else is trivial. You add a new element to the end of the array and "bubble it up" to restore the heap property. You remove the root, move the last element into its place, and "sift it down".

This MinHeap implementation shows the core logic.

class MinHeap {
  private heap: number[];

  constructor() {
    this.heap = [];
  }

  public peek(): number | undefined {
    return this.heap[0];
  }

  public insert(value: number): void {
    this.heap.push(value);
    this.heapifyUp();
  }

  public extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;

    const min = this.heap[0];
    const end = this.heap.pop();

    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.heapifyDown();
    }
    return min;
  }

  private heapifyUp(): void {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] < this.heap[parentIndex]) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  private heapifyDown(): void {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let smallestChildIndex = index;

      if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallestChildIndex]) {
        smallestChildIndex = leftChildIndex;
      }
      if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallestChildIndex]) {
        smallestChildIndex = rightChildIndex;
      }

      if (smallestChildIndex !== index) {
        [this.heap[index], this.heap[smallestChildIndex]] = [this.heap[smallestChildIndex], this.heap[index]];
        index = smallestChildIndex;
      } else {
        break;
      }
    }
  }
}

The extractMin operation is the most involved part. After removing the root, you replace it with the last element and then restore order by repeatedly swapping it with its smallest child until the heap property is satisfied.

Answering "Find the Kth Largest Element"

This is a classic heap problem. A naive solution is to sort the array (O(N log N)) and pick the Kth element from the end. You can do better.

The optimal approach uses a min-heap of size K.

  1. Initialize a min-heap.
  2. Iterate through the input array. For each number:
  3. If the heap has fewer than K elements, push the number onto the heap.
  4. If the heap has K elements and the current number is greater than the heap's minimum (heap.peek()), pop the minimum and push the current number.
  5. After iterating through all numbers, the root of the heap is the Kth largest element.

This works because the min-heap always holds the K largest numbers seen so far. The root is the smallest of those K numbers, which is exactly the Kth largest overall.

The time complexity is O(N log K) because you perform N operations, and each heap operation takes O(log K) time on a heap of size K. The space complexity is O(K) for storing the heap. This is a huge improvement over sorting when K is much smaller than N.

This same pattern applies to problems like finding the "Top K Frequent Elements" or designing a system to show the "Top 10 highest scores" on a leaderboard.

Heaps in Frontend Systems

While you won't be implementing requestAnimationFrame from scratch, the underlying schedulers often use priority queue concepts. Imagine a custom task scheduler for an application with many concurrent animations, data fetches, and user inputs.

A priority queue could manage these tasks. A high-priority animation update (e.g., for a user-dragged element) must be processed in the current frame, while a low-priority background data sync can wait. When a new task is scheduled, it's added to the priority queue. The event loop pulls the highest-priority task from the queue to execute next.

This is a strong system design talking point. It shows you can connect abstract data structures to real-world performance problems, like ensuring a smooth UI by prioritizing work that affects the current frame.

Try it

Modify the MinHeap code to create a MaxHeap. The only changes required are in the comparison operators inside heapifyUp and heapifyDown. Then, use your MaxHeap to solve Kth Largest Element in an Array in a different way: add all N elements to the MaxHeap and then extract the max K times. Compare the complexity of this approach to the O(N log K) min-heap method.

Next: Tries (Prefix Trees) for Autocomplete & Search.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Dynamic Programming I: Memoization

Next

Tries (Prefix Trees) for Autocomplete & Search