What Is a Priority Queue Data Structure? A Beginner's Guide

You're in a hospital emergency room. A dozen patients walk in. Some have a sprained ankle. One is having a cardiac arrest. The triage nurse doesn't call them in order of arrival. She calls the cardiac arrest first.

That's a priority queue. You get served based on urgency, not based on when you showed up.

A priority queue is a data structure where every element has a priority, and removal always returns the element with the highest priority, not the oldest one. Insert in any order. Extract and you always get the best one.

Also a priority queue: your task list on a Monday morning. In theory. In practice you're doing the easy stuff first. (That's a regular queue. We'll get to that.)

It shows up in interviews more than you'd expect, once you know what to look for.

How Is It Different from a Regular Queue?

A regular queue is FIFO: first in, first out. Insert at the back, remove from the front. Whoever arrived first leaves first. It is, bluntly, a line at the DMV.

A priority queue tears up the waiting list. Insert an element anywhere. When you remove, you always pull the minimum or maximum depending on how you set it up. The 47th element inserted can be removed first if its priority is best.

Insert and remove jump from O(1) to O(log n). That's the price of the ordering guarantee. If you never need priority ordering, use a plain queue and keep your O(1). Don't pay for what you don't need.

Inside the Priority Queue Data Structure

Priority queues are almost always implemented with a binary heap. That's why the two terms get conflated in interviews. When someone says "use a heap here," they mean a priority queue. Same thing, different name depending on who's talking.

A binary heap is a complete binary tree stored as a flat array where every parent satisfies the heap property with its children. A min-heap keeps the smallest element at the root. A max-heap keeps the largest. The heap data structure post covers the internals in depth, but for using a priority queue you mainly need to know:

• Insert: place the new element at the end of the array, then swap upward until the property is restored. O(log n).
• Remove: take the root, move the last element to the root, swap downward. O(log n).
• Peek: read the root without removing it. O(1).
• Build from an existing array: O(n). Floyd's build-heap algorithm processes the array bottom-up and beats the O(n log n) you'd get from inserting each element individually.

The same seven elements stored as a tree and as a flat array. Parent at index i has children at 2i+1 and 2i+2.

The Min vs Max Default Problem

Every major language ships a priority queue. None of them agree on which direction the priority runs.

Python and Java default to min-heap. C++ defaults to max-heap. This catches people in interviews constantly. Know your language's default before the interview starts.

It will catch you anyway. It catches everyone. The engineer who wrote the interview question was caught by it once.

import heapq

# Min-heap by default
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print(heapq.heappop(min_heap))  # 1

# Max-heap: negate every value
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
print(-heapq.heappop(max_heap))  # 5

# Build from an existing list: O(n)
data = [5, 1, 3, 2, 4]
heapq.heapify(data)
print(heapq.heappop(data))  # 1

Storing Objects with Custom Priority

Most interview problems don't push bare integers. They push graph nodes, tasks, coordinates. You need to tell the heap how to compare them.

In Python, push tuples. The heap compares tuples lexicographically, so the first element becomes the priority key.

import heapq

# (priority, value) -- first element drives ordering
tasks = []
heapq.heappush(tasks, (3, "low priority task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (2, "medium task"))

priority, task = heapq.heappop(tasks)
print(task)  # "urgent task"

# Dijkstra pattern: (distance, node_id)
heap = []
heapq.heappush(heap, (0, "start"))
heapq.heappush(heap, (7, "A"))
dist, node = heapq.heappop(heap)
print(node)  # "start"

In Java, pass a lambda or Comparator to the constructor.

// Sort by first element of each int[] pair: (distance, node)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{7, 1});
pq.offer(new int[]{2, 3});
int[] nearest = pq.poll();
System.out.println(nearest[1]); // node 3, distance 2

Three Patterns You'll Actually See in Interviews

Recognize these shapes and the data structure choice becomes automatic.

Top-K Elements

You want the K largest or K smallest values from a collection. Sort and slice is O(n log n). Maintaining a fixed-size heap of K elements does it in O(n log k).

For each new value, if it beats the current worst in the heap, pop the worst and push the new value. After n iterations, the heap holds the top K.

import heapq

def top_k_largest(nums: list[int], k: int) -> list[int]:
    min_heap: list[int] = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap

LeetCode 215 (Kth Largest Element), 347 (Top K Frequent Elements), and 973 (K Closest Points) are all this pattern with slight variations. The top-K heap pattern goes deeper on the variations.

Dijkstra's Shortest Path

Dijkstra's algorithm finds shortest paths in a weighted graph. The core operation: always process the unvisited node with the smallest known distance, then update its neighbors. "Always the smallest from a changing set" is exactly what a priority queue does.

Without one, you scan all unvisited nodes to find the minimum each step: O(V²). With a min-heap, each extraction is O(log V). Total: O((V + E) log V).

import heapq

def dijkstra(graph: dict, start: str) -> dict:
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    min_heap = [(0, start)]  # (distance, node)

    while min_heap:
        dist, node = heapq.heappop(min_heap)

        if dist > distances[node]:
            continue  # stale ghost entry from an earlier push

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(min_heap, (new_dist, neighbor))

    return distances

The if dist > distances[node]: continue guard is the lazy deletion pattern. When you find a shorter path to a node, you push a new entry rather than update the old one. The old entry becomes a ghost that gets skipped when it eventually surfaces. It's not elegant, but it's fast and dead simple to implement under pressure.

Merge K Sorted Lists

Given K sorted arrays or linked lists, produce one sorted output. Brute force dumps everything into one array and sorts: O(n log n) where n is total elements.

The heap approach runs O(n log K): maintain a min-heap of exactly K entries, one from the front of each list. Pop the minimum, append to output, push the next element from that same list. Each extraction costs O(log K), and you do n extractions.

This is LeetCode 23 directly, and the same idea appears in external merge sort and database merge operations. See more patterns in heap interview problems.

How to Recognize a Priority Queue Problem

Four signals:

1. The problem asks for K smallest or K largest elements, especially from a stream where you don't see all n upfront.
2. You're repeatedly finding the current minimum or maximum of a collection that keeps changing.
3. The problem involves event simulation, scheduling, or tasks with deadlines or weights.
4. You find yourself sorting inside a loop, or scanning an array for a minimum on each iteration.

That last one is the clearest tell. If your brute force scans an array for the minimum on each step, that's O(n) per step turning a problem into O(n²). A heap cuts each step to O(log n). The interviewer has been watching you write that inner loop and is now very patiently waiting for you to notice.

Space: the Quiet Win

A priority queue holding n elements uses O(n) space. The heap is a flat array. No surprises there.

The useful variation is the fixed-size heap from the Top-K pattern. Capping the heap at K elements bounds space to O(K). Finding the ten most frequent terms from a billion log entries uses O(10) heap space regardless of input size. That gap matters in real systems, and interviewers notice when you point it out. Most candidates state the time complexity and move on. Noting that the fixed-size heap also solves a memory constraint is the kind of thing that ends up in the write-up.

Checklist

• Priority queue removes by priority, not arrival order.
• Under the hood: binary heap. Insert and remove O(log n), peek O(1), build O(n).
• Python and Java: min-heap by default. C++: max-heap by default. Memorize this. You'll forget it. Memorize it again.
• Python: push tuples. Java: pass a Comparator.
• Three patterns: Top-K (fixed-size heap), Dijkstra (always extract minimum distance), Merge K Sorted (one element per list).
• Scanning for the minimum inside a loop is the clearest signal to reach for a heap.

If you want to practice explaining heap reasoning out loud and get feedback on whether your complexity analysis actually lands, SpaceComplexity runs voice-based mock interviews with rubric-based scoring across communication, problem-solving, and code quality.

Further Reading

• Priority queue (Wikipedia)
• heapq, Heap queue algorithm (Python 3 docs)
• PriorityQueue (Java SE 8 docs)
• std::priority_queue (cppreference.com)
• Priority Queue (GeeksforGeeks)