What is a heap / priority queue? | Interview Question

Q: What is a heap / priority queue?

**Target Audience:** Beginners preparing for coding interviews — you need Python lists and loops; no tree knowledge assumed. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Picture the waiting room of a hospital emergency department. Patients do not get seen in the order they walk in. A nurse gives each one a number for how urgent they are, and whenever a doctor becomes free, the **most urgent** patient goes next — even if they arrived five minutes ago and someone with a sprained wrist has been there for two hours. New patients keep arriving all the time, so the

The problem

Question presented to candidate: "What is a heap, and what is a priority queue? Explain how a binary heap is laid out, how push and pop work and what they cost, and show me how you would use one in Python — and how you would build one yourself if the library did not exist."

What a strong answer should cover:

A priority queue is the abstract type (insert, peek best, remove best); a binary heap is the usual implementation: a complete binary tree stored in a list.
The two rules (complete shape, parent ≤ child) and the index arithmetic: parent (i − 1) // 2, children 2i + 1 and 2i + 2.
Push = append + sift up, pop = move last to root + sift down, both O(log n); peek O(1); bottom-up heapify O(n).
A heap is only partly sorted: the root is the minimum, siblings are in no order, and popping everything gives heap sort.
Python specifics: heapq is a set of functions on a plain list and is a min-heap only; negate keys for a max-heap (or use the _max functions added in Python 3.14); push (priority, counter, item) tuples so ties never compare the items.

Code / implementation expected: Optional — be ready to write push and pop with sift up / sift down on a Python list, and to use heapq fluently.

heap
priority-queue

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need Python lists and loops; no tree knowledge assumed.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Picture the waiting room of a hospital emergency department. Patients do not get seen in the order they walk in. A nurse gives each one a number for how urgent they are, and whenever a doctor becomes free, the most urgent patient goes next — even if they arrived five minutes ago and someone

The solution is hidden so you can try first

15 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonA min-heap from scratch: push, sift up, pop, sift down

Practice

PythonHeapify vs n pushes (comparisons counted) and the built-in priority queue

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.