AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

07 Dictionaries and sets / Lesson 6 of 6

Choosing a collection — the complexity table and heapq

13 min · +10 XP · 2 exercises · 5 questions

Read the text13 min
Exercises0/2
Quiz5 q

Quick answer

When should I use a list, tuple, set or dict in Python?

Choose by the operations the problem needs. Use a dict or set to look things up by key or test membership often, both O(1) on average. Use a list for ordered data accessed by position and a tuple when it never changes; a deque for a queue, a heap from heapq for a repeated minimum, and a sorted list with bisect for binary search.

Every collection question in an interview comes down to a table: which operations does the problem need, and which structure does each of them in constant, logarithmic or linear time. Python ships six structures that cover almost everything — list, tuple, dict, set, deque, and the heap functions in heapq — plus bisect over a sorted list. This lesson gives the table, the decision rules that follow from it, the heapq API that has not appeared yet, and the memory picture that decides between a list of tuples and a dict of lists when both would work.

The table

Operationlisttupledictsetdequeheap (heapq on a list)sorted list + bisect
index x[i]O(1)O(1)O(1) by key—O(n) middle, O(1) ends—O(1)
x in cO(n)O(n)O(1)O(1)O(n)O(n)O(log n)
append / addO(1)—O(1)O(1)O(1) both endsO(log n) pushO(n) insort
pop endO(1)—O(1) popitemO(1) arbitraryO(1) both endsO(log n) pop minO(1)
insert / delete middleO(n)—O(1) by keyO(1)O(n)—O(n)
min / maxO(n)O(n)O(n)O(n)O(n)O(1) peek minO(1) ends
ordered iterationinsertioninsertioninsertionnoneinsertionnonesorted
lenO(1)O(1)O(1)O(1)O(1)O(1)O(1)

"Amortised" applies to list.append and dict/set insertion (occasional resizes); "average" to hashing (pathological collisions aside).

The decision rules

  • Need to look things up by a key or test membership many times? dict or set. A list scanned with in inside a loop is the most common quadratic bug in Python.
  • Need order of arrival and access by position? list; tuple if it never changes.
  • Need a queue (first in, first out) or a sliding window? deque — append and popleft. A list's pop(0) is O(n).
  • Need a stack (last in, first out)? list — append and pop.
  • Need the smallest (or largest) element repeatedly while elements keep arriving? A heap — heapq.heappush/heappop in O(log n). Sorting after every insert is O(n log n) each time.
  • Need sorted order with binary search, and inserts are rare? A sorted list with bisect.
  • Need to count or group? Counter, defaultdict (lesson 2).
  • Need order by key with fast insert and search? Python has no built-in balanced tree; a sorted list with bisect (O(n) insert) covers small cases, sortedcontainers (third-party) the large ones.

heapq

heapq turns a plain list into a binary min-heap: the smallest element is always h[0], push and pop are O(log n), and the list itself is the storage.

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
h[0]                        # 1 — peek the minimum without removing
heapq.heappop(h)            # 1
heapq.heapify(xs)           # turn an existing list into a heap in O(n)
heapq.heappushpop(h, x)     # push then pop, cheaper than the two calls
heapq.nsmallest(3, xs)      # the three smallest — O(n log k)
heapq.nlargest(3, xs, key=len)

There is no max-heap; push the negation (-x) or a tuple (-priority, item). Tuples give priority queues: heappush(h, (dist, node)) orders by distance first, and ties break on node — which must itself be comparable, or you insert a counter as the second element: (priority, count, item). Dijkstra, k-way merge, "top k" and event simulations are the heap's problems. Never iterate a heap expecting sorted order — only h[0] is guaranteed; pop repeatedly to get sorted output.

Memory, briefly

A list of n small ints is about 8n bytes of pointers plus the int objects; a dict is roughly three times a list of the same length because of its hash table; a set is similar to a dict; a tuple is slightly smaller than a list; array and NumPy store raw numbers at 4–8 bytes each with no per-element object. The consequence for design: a list of tuples [(name, score), …] is compact and fine for iteration; a dict {name: score} costs more but answers lookups — choose by the operations, and convert (dict(pairs)) when the access pattern changes.

Combining structures

Real solutions pair them: a deque for the BFS frontier and a set for visited; a dict from key to index and a list for order; a heap of (priority, item) and a dict of current priorities to detect stale entries; Counter for counts and heapq.nlargest for the top ones. The question is always "which operations, how often" — and the table answers it.

Pitfalls

  • x in list inside a loop.
  • list.pop(0) for a queue.
  • Re-sorting a list to get the minimum after each insert.
  • Pushing incomparable items into a heap as tuples without a tie-breaker.
  • Expecting heapq to give a max-heap or sorted iteration.
  • Choosing a dict for data that is only ever iterated in order.

Key takeaways

  • Lookup and membership: dict/set O(1). Position and order: list/tuple. Two-ended queue: deque. Repeated minimum: heap. Sorted with rare inserts: bisect.
  • list.pop(0), in on a list, and re-sorting per insert are the three quadratic habits to unlearn.
  • heapq is a min-heap over a list: heappush, heappop, h[0], heapify, nsmallest/nlargest; negate or use tuples for max and priorities, with a counter to break ties.
  • A dict costs about three times a list; choose by operations, convert when the access pattern changes.
  • Real solutions combine structures: frontier + visited, heap + dict, counter + top-k.

Common questions

How do I use heapq in Python?

heapq keeps a plain list as a binary min-heap: heappush(h, x) and heappop(h) run in O(log n), h[0] peeks at the smallest element, and heapify(xs) converts an existing list in O(n). nsmallest and nlargest return the top k items.

How do I make a max-heap in Python?

heapq provides only a min-heap, so push negated values, -x, and negate again when you pop, or push tuples such as (-priority, item). The smallest negated value is the largest original one.

How do I build a priority queue in Python?

Push (priority, item) tuples onto a list with heapq.heappush and take the lowest priority with heappop. When priorities tie the items are compared next, so add a counter as a tie-breaker, (priority, count, item), if the items are not comparable.

What is the time complexity of Python list, dict and set operations?

Indexing and appending to a list are O(1), but x in list, insert and pop(0) are O(n). Dict lookup, insertion and deletion, and set membership and insertion, are O(1) on average. A deque is O(1) at both ends, and a heap push or pop is O(log n).

Why is a heap not in sorted order when I iterate it?

A heap guarantees only that h[0] is the smallest element; the rest of the list is only partially ordered. To get sorted output, pop repeatedly with heappop, or sort the list.

Mark as readSign in to keep your place.

Python Data Structure Time Complexity and heapq Explained

Which Python collection to use: the Big-O of list, tuple, dict, set, deque, heap and bisect side by side, the decision rules, and heapq for priority queues.

  • Course: Python study plan
  • Module: Dictionaries and sets
  • Kind: Lesson
  • Reading time: 13 min
  • Runtime: CPython 3.11

When should I use a list, tuple, set or dict in Python?

Choose by the operations the problem needs. Use a dict or set to look things up by key or test membership often, both O(1) on average. Use a list for ordered data accessed by position and a tuple when it never changes; a deque for a queue, a heap from heapq for a repeated minimum, and a sorted list with bisect for binary search.

Lesson

Every collection question in an interview comes down to a table: which operations does the problem need, and which structure does each of them in constant, logarithmic or linear time. Python ships six structures that cover almost everything — list, tuple, dict, set, deque, and the heap functions in heapq — plus bisect over a sorted list. This lesson gives the table, the decision rules that follow from it, the heapq API that has not appeared yet, and the memory picture that decides between a list of tuples and a dict of lists when both would work.

The table

Operationlisttupledictsetdequeheap (heapq on a list)sorted list + bisect
index x[i]O(1)O(1)O(1) by key—O(n) middle, O(1) ends—O(1)
x in cO(n)O(n)O(1)O(1)O(n)O(n)O(log n)
append / addO(1)—O(1)O(1)O(1) both endsO(log n) pushO(n) insort
pop endO(1)—O(1) popitemO(1) arbitraryO(1) both endsO(log n) pop minO(1)
insert / delete middleO(n)—O(1) by keyO(1)O(n)—O(n)
min / maxO(n)O(n)O(n)O(n)O(n)O(1) peek minO(1) ends
ordered iterationinsertioninsertioninsertionnoneinsertionnonesorted
lenO(1)O(1)O(1)O(1)O(1)O(1)O(1)

"Amortised" applies to list.append and dict/set insertion (occasional resizes); "average" to hashing (pathological collisions aside).

The decision rules

  • Need to look things up by a key or test membership many times? dict or set. A list scanned with in inside a loop is the most common quadratic bug in Python.
  • Need order of arrival and access by position? list; tuple if it never changes.
  • Need a queue (first in, first out) or a sliding window? deque — append and popleft. A list's pop(0) is O(n).
  • Need a stack (last in, first out)? list — append and pop.
  • Need the smallest (or largest) element repeatedly while elements keep arriving? A heap — heapq.heappush/heappop in O(log n). Sorting after every insert is O(n log n) each time.
  • Need sorted order with binary search, and inserts are rare? A sorted list with bisect.
  • Need to count or group? Counter, defaultdict (lesson 2).
  • Need order by key with fast insert and search? Python has no built-in balanced tree; a sorted list with bisect (O(n) insert) covers small cases, sortedcontainers (third-party) the large ones.

heapq

heapq turns a plain list into a binary min-heap: the smallest element is always h[0], push and pop are O(log n), and the list itself is the storage.

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
h[0]                        # 1 — peek the minimum without removing
heapq.heappop(h)            # 1
heapq.heapify(xs)           # turn an existing list into a heap in O(n)
heapq.heappushpop(h, x)     # push then pop, cheaper than the two calls
heapq.nsmallest(3, xs)      # the three smallest — O(n log k)
heapq.nlargest(3, xs, key=len)

There is no max-heap; push the negation (-x) or a tuple (-priority, item). Tuples give priority queues: heappush(h, (dist, node)) orders by distance first, and ties break on node — which must itself be comparable, or you insert a counter as the second element: (priority, count, item). Dijkstra, k-way merge, "top k" and event simulations are the heap's problems. Never iterate a heap expecting sorted order — only h[0] is guaranteed; pop repeatedly to get sorted output.

Memory, briefly

A list of n small ints is about 8n bytes of pointers plus the int objects; a dict is roughly three times a list of the same length because of its hash table; a set is similar to a dict; a tuple is slightly smaller than a list; array and NumPy store raw numbers at 4–8 bytes each with no per-element object. The consequence for design: a list of tuples [(name, score), …] is compact and fine for iteration; a dict {name: score} costs more but answers lookups — choose by the operations, and convert (dict(pairs)) when the access pattern changes.

Combining structures

Real solutions pair them: a deque for the BFS frontier and a set for visited; a dict from key to index and a list for order; a heap of (priority, item) and a dict of current priorities to detect stale entries; Counter for counts and heapq.nlargest for the top ones. The question is always "which operations, how often" — and the table answers it.

Pitfalls

  • x in list inside a loop.
  • list.pop(0) for a queue.
  • Re-sorting a list to get the minimum after each insert.
  • Pushing incomparable items into a heap as tuples without a tie-breaker.
  • Expecting heapq to give a max-heap or sorted iteration.
  • Choosing a dict for data that is only ever iterated in order.

Key takeaways

  • Lookup and membership: dict/set O(1). Position and order: list/tuple. Two-ended queue: deque. Repeated minimum: heap. Sorted with rare inserts: bisect.
  • list.pop(0), in on a list, and re-sorting per insert are the three quadratic habits to unlearn.
  • heapq is a min-heap over a list: heappush, heappop, h[0], heapify, nsmallest/nlargest; negate or use tuples for max and priorities, with a counter to break ties.
  • A dict costs about three times a list; choose by operations, convert when the access pattern changes.
  • Real solutions combine structures: frontier + visited, heap + dict, counter + top-k.

Common questions

How do I use heapq in Python?

heapq keeps a plain list as a binary min-heap: heappush(h, x) and heappop(h) run in O(log n), h[0] peeks at the smallest element, and heapify(xs) converts an existing list in O(n). nsmallest and nlargest return the top k items.

How do I make a max-heap in Python?

heapq provides only a min-heap, so push negated values, -x, and negate again when you pop, or push tuples such as (-priority, item). The smallest negated value is the largest original one.

How do I build a priority queue in Python?

Push (priority, item) tuples onto a list with heapq.heappush and take the lowest priority with heappop. When priorities tie the items are compared next, so add a counter as a tie-breaker, (priority, count, item), if the items are not comparable.

What is the time complexity of Python list, dict and set operations?

Indexing and appending to a list are O(1), but x in list, insert and pop(0) are O(n). Dict lookup, insertion and deletion, and set membership and insertion, are O(1) on average. A deque is O(1) at both ends, and a heap push or pop is O(log n).

Why is a heap not in sorted order when I iterate it?

A heap guarantees only that h[0] is the smallest element; the rest of the list is only partially ordered. To get sorted output, pop repeatedly with heappop, or sort the list.

Exercises

Priority queue

Implement a priority queue on heapq from commands: push p task adds a task with integer priority p (smaller is more urgent); pop removes and prints the most urgent task — on equal priorities the one pushed first — or empty; peek prints it without removing (or empty). Store (priority, sequence, task) tuples so ties never compare the task text.

Input: commands. Output: one line per pop and peek.

push 2 write
push 1 read
push 2 test
pop
pop
peek
pop
pop

prints

read
write
test
test
empty

Top and bottom k

Read k and a line of words. Print the k longest words with heapq.nlargest and the k shortest with heapq.nsmallest, both using key=len — and, because the heap functions keep first-seen order on ties, print exactly what they return. Then print the k largest numbers from a third line of integers, descending.

Input: k, a line of words, a line of integers. Output: longest: <words>, shortest: <words>, largest: <numbers>.

2
fig banana kiwi apple
5 1 9 3

prints

longest: banana apple
shortest: fig kiwi
largest: 9 5

In this module: Dictionaries and sets

← Nested data and JSON · Checkpoint — Dictionaries and sets →