Use a heap when you repeatedly need the smallest or largest item while items keep arriving: each insert or removal costs O(log n). Use a sorted array when the data rarely changes and you need ranges, medians or the kth item directly, since any position reads in O(1). Keeping an array sorted costs O(n) per insert.
Heaps and sorted arrays compared
| Operation | Binary heap | Sorted array |
|---|---|---|
| Read the smallest or largest | O(1), one end only | O(1), both ends |
| Insert | O(log n) | O(n), shifting elements |
| Remove the top | O(log n) | O(1) from the end, O(n) from the front |
| Read the kth smallest | O(k log n), by popping | O(1) |
| Search for a value | O(n) | O(log n) |
| Range query | Not supported | O(log n + results) |
| Build from n items | O(n) | O(n log n) |
| List everything in order | O(n log n) | O(n) |
For Python, the bisect documentation confirms the sorted side: its insort functions are O(n), "because the logarithmic search step is dominated by the linear time insertion step." The heapq documentation gives heapify as linear and removing the smallest item as logarithmic. In Java, PriorityQueue gives O(log(n)) for offer and poll.
A worked example where both apply
Keep the three highest scores of a stream, reporting the current lowest of those three after each score. Both versions keep at most k items, so both use O(k) space.
import bisect
import heapq
def third_best_heap(scores, k=3):
heap, out = [], []
for s in scores:
heapq.heappush(heap, s)
if len(heap) > k:
heapq.heappop(heap) # O(log k): evict the smallest
out.append(heap[0] if len(heap) == k else None)
return out
def third_best_sorted(scores, k=3):
best, out = [], []
for s in scores:
bisect.insort(best, s) # O(k): shifts elements
if len(best) > k:
best.pop(0) # O(k): moves everything left
out.append(best[0] if len(best) == k else None)
return outFor n scores, the heap is O(n log k) and the sorted list is O(n · k). With k = 3 the difference is too small to matter, and the sorted list is arguably simpler. It also lets you read the whole top k in order at any moment, which the heap does not. As k grows, the heap wins. That is the kind of comparison an interviewer wants to hear, more than a flat claim that one is better.
Which to pick in an interview, and how to say why
- A stream, or many inserts mixed with "give me the next one": a heap.
- Data that arrives once and is then only read: sort it once. Binary search then answers everything.
- Ranges, the kth item or a median of static data: a sorted array.
- Both fast inserts and ranges: neither. That is a balanced tree, such as Java's TreeMap.
The scores keep arriving and I only ever need the current lowest of the top k, so I'll use a min-heap of size k: each score costs O(log k), so it's O(n log k) overall with O(k) space. A sorted array would make that read just as easy, but keeping it sorted costs O(k) per insert. If the data were static, I'd sort it once and use binary search, since a heap can't answer range questions.