Collections, Heapq & Itertools

Overview

Advanced collections (Counter, defaultdict, deque), priority heaps, and itertools speed up complex data operations.

Learning Objectives

• Group records using collections.defaultdict.
• Find Top-K elements using priority queues (heapq).
• Write lazy iterator chains using itertools.

Concept Explanation

The collections module provides structures like Counter (tallying frequencies), defaultdict (safe defaults), and deque (fast O(1) pops). heapq implements priority queues. itertools provides memory-efficient iterators.

Code Examples

Example 1 — Basics

This example introduces the fundamental syntax and concepts.

from collections import Counter
c = Counter('abacaba')
print(c['a']) # 4

Example 2 — Everyday Usage

This example demonstrates a realistic scenario handling business parameters.

import heapq
scores = [12, 3, 45, 9, 30]
# Retrieve top 3 scores
top_three = heapq.nlargest(3, scores)
print(top_three)

Example 3 — Advanced Example

This example shows clean, production-grade code structure following senior development standards.

from collections import defaultdict
import itertools

def group_anagrams(words):
    # Group sorted letter keys to original words
    grouped = defaultdict(list)
    for w in words:
        sorted_key = ''.join(sorted(w))
        grouped[sorted_key].append(w)
    return list(grouped.values())

print(group_anagrams(['eat', 'tea', 'tan', 'nat', 'bat']))

Visual Flow

The following execution flow represents the step-by-step evaluation inside the interpreter:

Unsorted List → heapify() → Construct Binary Min-Heap → heappop() → Retrieve Smallest Element in O(log N)

Common Mistakes

Review these common pitfalls when working with this topic:

• Using list.pop(0) instead of deque.popleft(), slowing down queue operations to O(N).
• Expecting heapq to maintain a sorted list internally (heaps are binary trees, not sorted lists).
• Forgetting that itertools iterators are exhausted after a single use.
• Negating values in heapq manually without using type safe helpers for custom comparisons.

Best Practices

Enforce these Pythonic best practices in your codebase:

q = []
q.append(x)
q.pop(0) # Slow O(N) queue pops

from collections import deque
q = deque()
q.append(x)
q.popleft() # Fast O(1) queue pops

Performance Notes

Keep these optimization guidelines in mind for performance-sensitive hotpaths:

• collections.deque has O(1) append and pop complexity on both ends.
• heapq.heappush() and heapq.heappop() run in O(log N) logarithmic time.
• itertools chain() combines iterables without copying their elements in memory.

Quick Revision

Use these key summaries for last-minute revision:

• Counter tallies frequency counts.
• defaultdict prevents KeyError lookups.
• deque provides fast O(1) double-ended pops.
• heapq implements binary min-heaps.
• Heaps run pushes/pops in O(log N).
• itertools supports lazy loop combinations.