DSA · Patterns, not puzzles

How does a heap back a priority queue?

Mediumheappriority-queuetreesUpdated Oct 2026

Short answer

A binary heap stores a complete tree in an array and keeps the smallest or largest element at the root. Push and pop are O(log n) and peek is O(1), which makes it the standard priority queue implementation.

A heap is not fully sorted. It only guarantees the parent-child ordering, which is enough to retrieve the extreme element quickly. The array representation avoids pointers: children of index i are at 2i + 1 and 2i + 2, and the parent is at floor((i - 1) / 2).

class MinHeap {
  constructor() {
    this.items = [];
  }

  push(value) {
    this.items.push(value);
    let index = this.items.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.items[parent] <= this.items[index]) break;
      [this.items[parent], this.items[index]] = [
        this.items[index],
        this.items[parent],
      ];
      index = parent;
    }
  }

  pop() {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = last;
      let index = 0;
      while (true) {
        const left = index * 2 + 1;
        const right = index * 2 + 2;
        let smallest = index;
        if (left < this.items.length && this.items[left] < this.items[smallest]) {
          smallest = left;
        }
        if (right < this.items.length && this.items[right] < this.items[smallest]) {
          smallest = right;
        }
        if (smallest === index) break;
        [this.items[index], this.items[smallest]] = [
          this.items[smallest],
          this.items[index],
        ];
        index = smallest;
      }
    }
    return top;
  }
}

Push bubbles up toward the root; pop moves the last element to the root and bubbles down.

Where priority queues are used

Dijkstra's algorithm for the next closest node
Prim's algorithm for the cheapest crossing edge
Top-k problems with a bounded heap
Task scheduling by priority
Merging k sorted lists

Building a heap from n elements with heapify is O(n), not O(n log n). Individual insertions are O(log n). If you only need the k largest elements, a min-heap of size k keeps memory at O(k).

A heap is not a binary search tree. Searching for an arbitrary value is O(n), because the heap ordering says nothing about siblings.

Follow-ups you should expect

Interviewers use these to check whether the first answer was understanding or memorisation.

1Why is heapify O(n) while n insertions are O(n log n)?
2How do you get the k largest elements efficiently?
3Why can't you binary search a heap?
4How would you implement a max-heap in JavaScript?

Say it in the interview

A binary heap is a complete tree stored in an array that keeps the parent-child order, so the root is the minimum or maximum. Push and pop are O(log n) because they bubble up or down one path, and peek is O(1). I use it for Dijkstra, Prim, top-k and scheduling, and I remember it is not sorted, so searching for an arbitrary value is linear.

Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.

Now say it out loud.

Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.

Start a free DSA interview Browse all questions

Where priority queues are used

Follow-ups you should expect

Related questions

Now say it out loud.