A strong answer
A priority queue needs push, pop-the-minimum and peek. An unsorted array makes pop O(n); a sorted array makes push O(n); a balanced search tree gives O(log n) for both but carries pointers, per-node allocation and rebalancing. A binary heap gives O(log n) push and pop and O(1) peek with nothing but an array.
It keeps two invariants. Shape: it is a complete binary tree, so it can be stored level by level in an array with no gaps, where the children of index i are at 2i + 1 and 2i + 2 and its parent at (i − 1) // 2. Order: every parent is no bigger than its children (for a min-heap), so the minimum is at index 0. Push appends at the end and sifts up; pop moves the last element to the root and sifts down toward the smaller child. Both walk one path of a tree whose height is ⌊log₂ n⌋. Building a heap from n items with bottom-up heapify is O(n).
The heap is the wrong tool when you need to find or delete arbitrary items, iterate in sorted order, or get both the minimum and the maximum: then a balanced BST fits better. Changing an item's priority needs either an index map from item to array position, so it can be sifted in place, or lazy deletion, pushing a new entry and skipping stale ones when popped. In practice, d-ary heaps with 4 children per node are often faster for large heaps, because the tree is shallower and the children of a node share a cache line.
What the interviewer is listening for
- A comparison of alternatives with their costs.
- The array layout with correct index formulas, and the two invariants.
- Limits of the heap, and how to handle priority updates.
Common mistakes
- Saying a heap is sorted, or that it supports O(log n) search.
- Forgetting that push and pop need sift-up and sift-down, not a re-sort.
- Getting the default direction of the language's heap wrong.