Pick the structure from the operations and their required cost. This chapter is a checklist, not new code tricks.

Goal

Print a recommended structure for four kiosk jobs.

The jobs

jobs = [
    ("index the 3rd product", "list"),
    ("lookup price by product id", "dict"),
    ("next customer in line", "deque"),
    ("nearest restock by km", "heap"),
]
for job, rec in jobs:
    print(job, "->", rec)

Cost cheat sheet

rows = [
    ("list[i]", "Θ(1)"),
    ("list insert at 0", "Θ(n)"),
    ("deque popleft", "Θ(1)"),
    ("dict get", "Θ(1) avg"),
    ("heap push/pop", "Θ(log n)"),
    ("BST search (balanced)", "Θ(log n)"),
    ("BST search (sorted inserts)", "Θ(n)"),
    ("DFS/BFS on V,E", "Θ(V+E)"),
]
for op, cost in rows:
    print(f"{op:28} {cost}")

A wrong pick

# Finding min km by scanning a list every time:
stock = [("Nakuru", 160), ("Mombasa", 480), ("Eldoret", 160)]
steps = 0
best = stock[0]
for row in stock:
    steps += 1
    if row[1] < best[1]:
        best = row
print("scan min", best, "steps", steps)

Fine for 3 rows. For 10_000 restock events, push them on a heap as they arrive.

Pitfall

“I know dicts” is not a design. If you need order-by-priority, a dict of distances still wants a heap (Dijkstra). If you need sorted iteration of keys, a dict does not give you that for free — sort or use a tree.