collections, heapq and Choosing a Structure
40 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Interviewers ask 'which structure would you use?' more often than 'how does it work?'. The answer comes from the operations you need: count, group, take from both ends, or always get the smallest item.
Counter and defaultdict
A Counter is a dict subclass that counts hashable items. A missing item has count 0, and most_common(n) lists the n highest counts.
Counting and grouping are so common that the standard library has tools for them. A Counter counts items. A defaultdict builds a missing value on first use.
from collections import Counter, defaultdictwords = ['tea', 'cup', 'tea', 'pen', 'tea', 'cup']print(Counter(words).most_common(2))groups = defaultdict(list)for w in words: groups[len(w)].append(w)print(dict(groups))Example 1 · Counter basics
from collections import Counterc = Counter('banana')print(c)print(c.most_common(2))print(c['z'])c.update('aa')print(c['a'])Counter({'a': 3, 'n': 2, 'b': 1})
[('a', 3), ('n', 2)]
0
5What this code does
- Counter prints items by count, highest first.
- A missing item reads as 0 without being added.
- update adds to the existing counts.
Example 2 · defaultdict creates on read
from collections import defaultdictorders = defaultdict(list)for who, item in [('Asha', 'pen'), ('Ravi', 'book'), ('Asha', 'cup')]: orders[who].append(item)print(dict(orders))count = defaultdict(int)count['missing']print(len(count)){'Asha': ['pen', 'cup'], 'Ravi': ['book']}
1What this code does
- Each missing customer starts with an empty list.
- Reading a missing key adds it, so the length is 1.
A Counter is a dict that returns 0 for a missing item and adds counts together. defaultdict(list) calls list() when a key is missing. One trap: reading d[k] on a defaultdict creates the key, so a typo can add keys silently.
deque for queues
A deque is a double-ended queue. Adding and removing at either end takes O(1) time, but reading from the middle takes O(n).
A list is slow at the front because every item must shift. A deque (double-ended queue) adds and removes at both ends in constant time.
from collections import dequeline = deque(['A-1', 'A-2'])line.append('A-3')line.appendleft('A-0')print(line.popleft(), line.pop(), line)recent = deque(maxlen=2)for n in (1, 2, 3): recent.append(n)print(recent)Example 3 · deque at both ends
from collections import dequed = deque([1, 2, 3])d.appendleft(0)d.append(4)print(d.popleft(), d.pop(), d)recent = deque(maxlen=3)for i in range(5): recent.append(i)print(recent)0 4 deque([1, 2, 3]) deque([2, 3, 4], maxlen=3)
What this code does
- popleft and pop remove from each end in O(1).
- With maxlen=3 only the newest three values remain.
A deque is stored as linked blocks, so both ends are O(1). Indexing in the middle is O(n). With maxlen, an append on a full deque drops an item from the other end, which suits 'last n' windows. Use deque for queues, a plain list for stacks.
heapq and priority queues
A heap is a tree stored in a list where every parent is smaller than or equal to its children, so the smallest item is always at index 0.
A heap always gives the smallest item first. Python's heapq works on an ordinary list. Pushing and popping cost O(log n); reading the smallest costs O(1).
import heapqheap = []for x in (5, 1, 8, 3): heapq.heappush(heap, x)print(heap[0])print([heapq.heappop(heap) for _ in range(4)])print(heapq.nlargest(2, [4, 9, 1, 7]))Example 4 · heapq as min-heap and max-heap
import heapqh = []for x in [5, 1, 8, 3]: heapq.heappush(h, x)print(h[0])print([heapq.heappop(h) for _ in range(4)])mh = []for x in [5, 1, 8, 3]: heapq.heappush(mh, -x)print(-mh[0])1 [1, 3, 5, 8] 8
What this code does
- heap[0] is the smallest item.
- Popping repeatedly returns the items in sorted order.
- Negating values turns the min-heap into a max-heap.
Example 5 · A priority queue of tickets
import heapqtickets = []heapq.heappush(tickets, (2, 'reset password'))heapq.heappush(tickets, (1, 'payment failed'))heapq.heappush(tickets, (2, 'update address'))while tickets: priority, text = heapq.heappop(tickets) print(priority, text)1 payment failed 2 reset password 2 update address
What this code does
- Tuples compare from the first item, so the lowest priority number comes out first.
- On equal priority, the text decides the order.
heapq is a min-heap. For a max-heap, push negated numbers. The list is not sorted: only heap[0] is guaranteed to be the smallest. heapify(list) builds a heap in O(n). For a priority queue, push tuples like (priority, name).
Choosing a structure
Start from the operation that must be fast, then pick the structure. Membership tests use a set. Lookup by key uses a dict. Taking from both ends uses a deque. Always getting the smallest item uses a heap. Counting uses a Counter.
When two answers work, say the cost of each in plain words and name the operation you optimized. If you need a sorted sequence with fast inserts, the standard library has only bisect.insort, which is O(n) per insert.
Next step
Check your understanding
12 quick questions