Technical interview guide

Heaps / Priority Queues

A tree-shaped structure that keeps the min (or max) element accessible in O(1), with O(log n) insert and remove.

Read: 42 min
Practice MCQs: 25
Interview QA: 25
Edition: v7
Editorial status: Reviewed
Relevant for: AI EngineerBackend EngineerBlockchain DeveloperComputational BiologistData ScientistEmbedded Systems EngineerFrontend EngineerFull-Stack DeveloperMachine Learning EngineerQuantum Software EngineerRobotics EngineerSoftware Engineer

Scope: Language-neutral, with library behaviour cited from CPython 3.14 heapq, the C++ standard containers, and java.util as of Java 21.

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-05 · Written: 2026-10-05 · Reviewed: 2026-10-03

QA-1

Explain the heap invariant and how it changes a production decision.

QA-2

How would you reason about the array layout in a system you own?

QA-3

Walk through sift-up and sift-down, including where engineers most often get it wrong.

QA-4

What does linear-time heapify guarantee, and what does it deliberately leave open?

QA-5

How do min-heaps and max-heaps differ in their invariants, how do peek, push, and pop operate on each, and what are their exact time and space complexities?

QA-6

Where does top-k versus sorting versus selection matter, and where is it irrelevant?

QA-7

A teammate proposes a design that hinges on the top-k pattern. How do you evaluate it?

QA-8

Teach streaming medians to an engineer who has only seen it as a rule of thumb.

QA-9

How do you merge K sorted lists or streams using a min-heap, and what are the time and space complexity tradeoffs compared to pairwise merging?

QA-10

How does an indexed priority queue or standard min-heap optimize Dijkstra's shortest path algorithm, and what is the difference between lazy deletion and decrease-key?

QA-11

How do you implement an efficient decrease-key operation in a binary min-heap, and why does standard Dijkstra's algorithm often prefer lazy deletion over an explicit decrease-key?

QA-12

How does lazy deletion change if the workload grows by two orders of magnitude?

QA-13

A vendor promises heapsort is handled for you. What do you still own?

QA-14

When would you refuse a design because of stability and ties?

QA-15

How would you explain comparing non-comparable payloads without using the usual slogan?

QA-16

What failure would you inject to check a team's understanding of d-ary heaps?

QA-17

How should on-call treat an alert that names fibonacci heaps in theory and practice as the cause?

QA-18

What belongs in a runbook section on bounded heaps and backpressure, and what does not?

QA-19

How would you review a pull request whose risk is priority inversion and starvation?

QA-20

What trade-off does the oldest-item metric force that a junior answer usually skips?

QA-21

How would you brief product on why concurrent priority queues delays a ship date?

QA-22

What is the smallest experiment that would change your mind about heaps versus balanced trees?

QA-23

How does peek, pop, and the empty case interact with rollback, and where do people ignore that?

QA-24

What would you ask a candidate who recites complexity summary but cannot apply it?

QA-25