Utilities
Bisect and Heapq Modules
Finding insertion points in sorted lists or maintaining a priority queue are common operations that naive implementations handle inefficiently. The bisect and heapq modules provide O(log n) algorithms for binary search and heap operations, essential for scheduling, ranking, and sorted data maintenance.
binary search
An O(log n) algorithm that finds positions in sorted sequences by repeatedly halving the search space - much faster than linear search for large data.
Bisect Operations
Find insertion points in sorted lists:
bisect.py
Replay: real traced execution (multi-file project)
"""bisect module examples"""
import bisect
# bisect_left vs bisect_right
print("bisect_left vs bisect_right:")
numbers = [1, 3, 3, 3, 5, 7, 9]
value = 3
# Find leftmost position
left = bisect.bisect_left(numbers, value)
print(f"bisect_left({numbers}, {value}): {left}")
print(f" Would insert at index {left} (before existing 3s)")
# Find rightmost position
right = bisect.bisect_right(numbers, value)
print(f"bisect_right({numbers}, {value}): {right}")
print(f" Would insert at index {right} (after existing 3s)")
# bisect is alias for bisect_right
regular = bisect.bisect(numbers, value)
print(f"bisect (same as bisect_right): {regular}")
# Find insertion point
print("\nFind insertion point:")
sorted_list = [10, 20, 30, 40, 50]
for value in [15, 25, 35, 5, 60]:
pos = bisect.bisect_left(sorted_list, value)
print(f"Insert {value} at index {pos}: {sorted_list[:pos] + [value] + sorted_list[pos:]}")
# Check if element exists
print("\nCheck if element exists:")
numbers = [1, 3, 5, 7, 9, 11, 13]
def contains(sorted_list, value):
"""Check if value is in sorted list using binary search"""
i = bisect.bisect_left(sorted_list, value)
return i < len(sorted_list) and sorted_list[i] == value
for val in [5, 6, 13, 14]:
exists = contains(numbers, val)
print(f"{val} in list: {exists}")
# Find range of values
print("\nFind range of values:")
numbers = [1, 2, 2, 2, 3, 3, 4, 5]
value = 2
# Find range of all 2s
start = bisect.bisect_left(numbers, value)
end = bisect.bisect_right(numbers, value)
print(f"Numbers: {numbers}")
print(f"Value {value} appears at indices [{start}:{end})")
print(f"Count: {end - start}")
print(f"Elements: {numbers[start:end]}")
# Grades example
print("\nGrades example:")
# Grade boundaries
breakpoints = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']
def get_grade(score):
"""Convert score to letter grade"""
i = bisect.bisect(breakpoints, score)
return grades[i]
scores = [55, 65, 75, 85, 95, 100]
for score in scores:
grade = get_grade(score)
print(f"Score {score}: {grade}")
# Percentile calculation
print("\nPercentile calculation:")
data = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
def percentile_rank(sorted_data, value):
"""Calculate percentile rank of value"""
i = bisect.bisect_right(sorted_data, value)
return (i / len(sorted_data)) * 100
print(f"Data: {data}")
for val in [15, 20, 25, 30, 42]:
rank = percentile_rank(data, val)
print(f"Value {val}: {rank:.1f}th percentile")
# Find closest value
print("\nFind closest value:")
numbers = [10, 20, 30, 40, 50, 60]
def find_closest(sorted_list, target):
"""Find closest value to target"""
i = bisect.bisect_left(sorted_list, target)
if i == 0:
return sorted_list[0]
if i == len(sorted_list):
return sorted_list[-1]
# Check which is closer
before = sorted_list[i - 1]
after = sorted_list[i]
if target - before < after - target:
return before
else:
return after
for target in [15, 25, 35, 5, 65]:
closest = find_closest(numbers, target)
print(f"Closest to {target}: {closest}")
# Range search
print("\nRange search:")
numbers = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
def find_range(sorted_list, low, high):
"""Find all values in range [low, high)"""
start = bisect.bisect_left(sorted_list, low)
end = bisect.bisect_left(sorted_list, high)
return sorted_list[start:end]
result = find_range(numbers, 15, 35)
print(f"Values in [15, 35): {result}")
result = find_range(numbers, 20, 40)
print(f"Values in [20, 40): {result}")
# Custom key function
print("\nCustom key function:")
# Sort by absolute value
numbers = [-10, -5, 0, 3, 7, 12]
target = -6
# Find where to insert -6 when sorted by absolute value
abs_numbers = [abs(x) for x in numbers]
pos = bisect.bisect_left(abs_numbers, abs(target))
print(f"Original: {numbers}")
print(f"Sorted by abs: {abs_numbers}")
print(f"Insert {target} at position {pos}")
"""bisect module examples"""
import bisect
# bisect_left vs bisect_right
print("bisect_left vs bisect_right:")
numbers = [1, 3, 3, 3, 5, 7, 9]
value = 2
# Find leftmost position
left = bisect.bisect_left(numbers, value)
print(f"bisect_left({numbers}, {value}): {left}")
print(f" Would insert at index {left} (before existing 3s)")
# Find rightmost position
right = bisect.bisect_right(numbers, value)
print(f"bisect_right({numbers}, {value}): {right}")
print(f" Would insert at index {right} (after existing 3s)")
# bisect is alias for bisect_right
regular = bisect.bisect(numbers, value)
print(f"bisect (same as bisect_right): {regular}")
# Find insertion point
print("\nFind insertion point:")
sorted_list = [10, 20, 30, 40, 50]
for value in [15, 25, 35, 5, 60]:
pos = bisect.bisect_left(sorted_list, value)
print(f"Insert {value} at index {pos}: {sorted_list[:pos] + [value] + sorted_list[pos:]}")
# Check if element exists
print("\nCheck if element exists:")
numbers = [1, 3, 5, 7, 9, 11, 13]
def contains(sorted_list, value):
"""Check if value is in sorted list using binary search"""
i = bisect.bisect_left(sorted_list, value)
return i < len(sorted_list) and sorted_list[i] == value
for val in [5, 6, 13, 14]:
exists = contains(numbers, val)
print(f"{val} in list: {exists}")
# Find range of values
print("\nFind range of values:")
numbers = [1, 2, 2, 2, 3, 3, 4, 5]
value = 2
# Find range of all 2s
start = bisect.bisect_left(numbers, value)
end = bisect.bisect_right(numbers, value)
print(f"Numbers: {numbers}")
print(f"Value {value} appears at indices [{start}:{end})")
print(f"Count: {end - start}")
print(f"Elements: {numbers[start:end]}")
# Grades example
print("\nGrades example:")
# Grade boundaries
breakpoints = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']
def get_grade(score):
"""Convert score to letter grade"""
i = bisect.bisect(breakpoints, score)
return grades[i]
scores = [55, 65, 75, 85, 95, 100]
for score in scores:
grade = get_grade(score)
print(f"Score {score}: {grade}")
# Percentile calculation
print("\nPercentile calculation:")
data = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
def percentile_rank(sorted_data, value):
"""Calculate percentile rank of value"""
i = bisect.bisect_right(sorted_data, value)
return (i / len(sorted_data)) * 100
print(f"Data: {data}")
for val in [15, 20, 25, 30, 42]:
rank = percentile_rank(data, val)
print(f"Value {val}: {rank:.1f}th percentile")
# Find closest value
print("\nFind closest value:")
numbers = [10, 20, 30, 40, 50, 60]
def find_closest(sorted_list, target):
"""Find closest value to target"""
i = bisect.bisect_left(sorted_list, target)
if i == 0:
return sorted_list[0]
if i == len(sorted_list):
return sorted_list[-1]
# Check which is closer
before = sorted_list[i - 1]
after = sorted_list[i]
if target - before < after - target:
return before
else:
return after
for target in [15, 25, 35, 5, 65]:
closest = find_closest(numbers, target)
print(f"Closest to {target}: {closest}")
# Range search
print("\nRange search:")
numbers = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
def find_range(sorted_list, low, high):
"""Find all values in range [low, high)"""
start = bisect.bisect_left(sorted_list, low)
end = bisect.bisect_left(sorted_list, high)
return sorted_list[start:end]
result = find_range(numbers, 15, 35)
print(f"Values in [15, 35): {result}")
result = find_range(numbers, 20, 40)
print(f"Values in [20, 40): {result}")
# Custom key function
print("\nCustom key function:")
# Sort by absolute value
numbers = [-10, -5, 0, 3, 7, 12]
target = -6
# Find where to insert -6 when sorted by absolute value
abs_numbers = [abs(x) for x in numbers]
pos = bisect.bisect_left(abs_numbers, abs(target))
print(f"Original: {numbers}")
print(f"Sorted by abs: {abs_numbers}")
print(f"Insert {target} at position {pos}")
"""bisect module examples"""
import bisect
# bisect_left vs bisect_right
print("bisect_left vs bisect_right:")
numbers = [1, 3, 3, 3, 5, 7, 9]
value = 5
# Find leftmost position
left = bisect.bisect_left(numbers, value)
print(f"bisect_left({numbers}, {value}): {left}")
print(f" Would insert at index {left} (before existing 3s)")
# Find rightmost position
right = bisect.bisect_right(numbers, value)
print(f"bisect_right({numbers}, {value}): {right}")
print(f" Would insert at index {right} (after existing 3s)")
# bisect is alias for bisect_right
regular = bisect.bisect(numbers, value)
print(f"bisect (same as bisect_right): {regular}")
# Find insertion point
print("\nFind insertion point:")
sorted_list = [10, 20, 30, 40, 50]
for value in [15, 25, 35, 5, 60]:
pos = bisect.bisect_left(sorted_list, value)
print(f"Insert {value} at index {pos}: {sorted_list[:pos] + [value] + sorted_list[pos:]}")
# Check if element exists
print("\nCheck if element exists:")
numbers = [1, 3, 5, 7, 9, 11, 13]
def contains(sorted_list, value):
"""Check if value is in sorted list using binary search"""
i = bisect.bisect_left(sorted_list, value)
return i < len(sorted_list) and sorted_list[i] == value
for val in [5, 6, 13, 14]:
exists = contains(numbers, val)
print(f"{val} in list: {exists}")
# Find range of values
print("\nFind range of values:")
numbers = [1, 2, 2, 2, 3, 3, 4, 5]
value = 2
# Find range of all 2s
start = bisect.bisect_left(numbers, value)
end = bisect.bisect_right(numbers, value)
print(f"Numbers: {numbers}")
print(f"Value {value} appears at indices [{start}:{end})")
print(f"Count: {end - start}")
print(f"Elements: {numbers[start:end]}")
# Grades example
print("\nGrades example:")
# Grade boundaries
breakpoints = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']
def get_grade(score):
"""Convert score to letter grade"""
i = bisect.bisect(breakpoints, score)
return grades[i]
scores = [55, 65, 75, 85, 95, 100]
for score in scores:
grade = get_grade(score)
print(f"Score {score}: {grade}")
# Percentile calculation
print("\nPercentile calculation:")
data = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
def percentile_rank(sorted_data, value):
"""Calculate percentile rank of value"""
i = bisect.bisect_right(sorted_data, value)
return (i / len(sorted_data)) * 100
print(f"Data: {data}")
for val in [15, 20, 25, 30, 42]:
rank = percentile_rank(data, val)
print(f"Value {val}: {rank:.1f}th percentile")
# Find closest value
print("\nFind closest value:")
numbers = [10, 20, 30, 40, 50, 60]
def find_closest(sorted_list, target):
"""Find closest value to target"""
i = bisect.bisect_left(sorted_list, target)
if i == 0:
return sorted_list[0]
if i == len(sorted_list):
return sorted_list[-1]
# Check which is closer
before = sorted_list[i - 1]
after = sorted_list[i]
if target - before < after - target:
return before
else:
return after
for target in [15, 25, 35, 5, 65]:
closest = find_closest(numbers, target)
print(f"Closest to {target}: {closest}")
# Range search
print("\nRange search:")
numbers = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
def find_range(sorted_list, low, high):
"""Find all values in range [low, high)"""
start = bisect.bisect_left(sorted_list, low)
end = bisect.bisect_left(sorted_list, high)
return sorted_list[start:end]
result = find_range(numbers, 15, 35)
print(f"Values in [15, 35): {result}")
result = find_range(numbers, 20, 40)
print(f"Values in [20, 40): {result}")
# Custom key function
print("\nCustom key function:")
# Sort by absolute value
numbers = [-10, -5, 0, 3, 7, 12]
target = -6
# Find where to insert -6 when sorted by absolute value
abs_numbers = [abs(x) for x in numbers]
pos = bisect.bisect_left(abs_numbers, abs(target))
print(f"Original: {numbers}")
print(f"Sorted by abs: {abs_numbers}")
print(f"Insert {target} at position {pos}")
numbers ← [1, 3, 3, 3, 5, 7, 9], value ← 3, left ← 1, right ← 4
1"""bisect module examples"""23import bisect45# bisect_left vs bisect_right6print("bisect_left vs bisect_right:")78numbers→ [1, 3, 3, 3, 5, 7, 9] = [1, 3, 3, 3, 5, 7, 9]9value→ 3 = 3 #@value=2, 51011# Find leftmost position12left→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 3, 3, 3, 5, 7, 9], value3)13print(f"bisect_left({numbers[1, 3, 3, 3, 5, 7, 9]}, {value3}): {left1}")14print(f" Would insert at index {left1} (before existing 3s)")1516# Find rightmost position17right→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 3, 3, 3, 5, 7, 9], value3)18print(f"bisect_right({numbers[1, 3, 3, 3, 5, 7, 9]}, {value3}): {right4}")19print(f" Would insert at index {right4} (after existing 3s)")2021# bisect is alias for bisect_right22regular→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(numbers[1, 3, 3, 3, 5, 7, 9], value3)23print(f"bisect (same as bisect_right): {regular4}")2425# Find insertion point26print("\nFind insertion point:")2728sorted_list→ [10, 20, 30, 40, 50] = [10, 20, 30, 40, 50]outputbisect_left vs bisect_right: bisect_left([1, 3, 3, 3, 5, 7, 9], 3): 1 Would insert at index 1 (before existing 3s) bisect_right([1, 3, 3, 3, 5, 7, 9], 3): 4 Would insert at index 4 (after existing 3s) bisect (same as bisect_right): 4 Find insertion point:pos ← 1
pass 1 of 530for value15 in [15, 25, 35, 5, 60]:31 pos→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50], value15)32 print(f"Insert {value15} at index {pos1}: {sorted_list[:pos][10] + [value] + sorted_list[pos:][20, 30, 40, 50]}")outputInsert 15 at index 1: [10, 15, 20, 30, 40, 50]All 5 passes — pass 1 is the card above pass valuesorted_list[:pos]sorted_list[pos:]pos1 15 [10] [20, 30, 40, 50] 1 2 25 [10, 20] [30, 40, 50] 2 3 35 [10, 20, 30] [40, 50] 3 4 5 [] [10, 20, 30, 40, 50] 0 5 60 [10, 20, 30, 40, 50] [] 5 numbers ← [1, 3, 5, 7, 9, 11, 13]
34# Check if element exists35print("\nCheck if element exists:")3637numbers→ [1, 3, 5, 7, 9, 11, 13] = [1, 3, 5, 7, 9, 11, 13]output Check if element exists:for val in [5, 6, 13, 14]:
pass 1 of 444for val5 in [5, 6, 13, 14]:45 exists = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val} in list: {exists}")All 4 passes — pass 1 is the card above pass val1 5 2 6 3 13 4 14 i ← 2
pass 1 of 439def contains(sorted_list[1, 3, 5, 7, 9, 11, 13], value5):40 """Check if value is in sorted list using binary search"""41 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[1, 3, 5, 7, 9, 11, 13], value5)42 return i2 < len(sorted_list[1, 3, 5, 7, 9, 11, 13]) and sorted_list[i]5 == value5All 4 passes — pass 1 is the card above pass valuesorted_list[i]i1 5 5 2 2 6 7 3 3 13 13 6 4 14 (empty) 7 exists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val5} in list: {existsTrue}")output5 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val6)46 print(f"{val6} in list: {existsFalse}")output6 in list: Falseexists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val13)46 print(f"{val13} in list: {existsTrue}")output13 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val14)46 print(f"{val14} in list: {existsFalse}")output14 in list: Falsenumbers ← [1, 2, 2, 2, 3, 3, 4, 5], value ← 2, start ← 1, end ← 4
48# Find range of values49print("\nFind range of values:")5051numbers→ [1, 2, 2, 2, 3, 3, 4, 5] = [1, 2, 2, 2, 3, 3, 4, 5]52value→ 2 = 25354# Find range of all 2s55start→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)56end→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)5758print(f"Numbers: {numbers[1, 2, 2, 2, 3, 3, 4, 5]}")59print(f"Value {value2} appears at indices [{start1}:{end4})")60print(f"Count: {end4 - start1}")61print(f"Elements: {numbers[start:end][2, 2, 2]}")6263# Grades example64print("\nGrades example:")6566# Grade boundaries67breakpoints→ [60, 70, 80, 90] = [60, 70, 80, 90]68grades→ ['F', 'D', 'C', 'B', 'A'] = ['F', 'D', 'C', 'B', 'A']6970def get_grade(score):71 """Convert score to letter grade"""72 i = bisect.bisect(breakpoints, score)73 return grades[i]7475scores→ [55, 65, 75, 85, 95, 100] = [55, 65, 75, 85, 95, 100]76for score in scores:output Find range of values: Numbers: [1, 2, 2, 2, 3, 3, 4, 5] Count: 3 Elements: [2, 2, 2] Grades example:for score in scores:
pass 1 of 675scores = [55, 65, 75, 85, 95, 100]76for score55 in scores[55, 65, 75, 85, 95, 100]:77 grade = get_grade(score55)78 print(f"Score {score}: {grade}")All 6 passes — pass 1 is the card above pass score1 55 2 65 3 75 4 85 5 95 6 100 i ← 0
pass 1 of 670def get_grade(score55):71 """Convert score to letter grade"""72 i→ 0 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(breakpoints[60, 70, 80, 90], score55)73 return grades[i]FAll 6 passes — pass 1 is the card above pass scoregrades[i]i1 55 F 0 2 65 D 1 3 75 C 2 4 85 B 3 5 95 A 4 6 100 A 4 grade ← F
76for score in scores:77 grade→ F = get_grade(score55)78 print(f"Score {score55}: {gradeF}")outputScore 55: Fgrade ← D
76for score in scores:77 grade→ D = get_grade(score65)78 print(f"Score {score65}: {gradeD}")outputScore 65: Dgrade ← C
76for score in scores:77 grade→ C = get_grade(score75)78 print(f"Score {score75}: {gradeC}")outputScore 75: Cgrade ← B
76for score in scores:77 grade→ B = get_grade(score85)78 print(f"Score {score85}: {gradeB}")outputScore 85: Bgrade ← A
76for score in scores:77 grade→ A = get_grade(score95)78 print(f"Score {score95}: {gradeA}")outputScore 95: Agrade ← A
76for score in scores:77 grade→ A = get_grade(score100)78 print(f"Score {score100}: {gradeA}")outputScore 100: Adata ← [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
80# Percentile calculation81print("\nPercentile calculation:")8283data→ [12, 15, 18, 20, 22, 25, 28, 30, 35, 40] = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]8485def percentile_rank(sorted_data, value):86 """Calculate percentile rank of value"""87 i = bisect.bisect_right(sorted_data, value)88 return (i / len(sorted_data)) * 1008990print(f"Data: {data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40]}")91for val in [15, 20, 25, 30, 42]:output Percentile calculation: Data: [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]for val in [15, 20, 25, 30, 42]:
pass 1 of 590print(f"Data: {data}")91for val15 in [15, 20, 25, 30, 42]:92 rank = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val}: {rank:.1f}th percentile")All 5 passes — pass 1 is the card above pass val1 15 2 20 3 25 4 30 5 42 i ← 2
pass 1 of 585def percentile_rank(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15):86 """Calculate percentile rank of value"""87 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15)88 return (i2 / len(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40])) * 100All 5 passes — pass 1 is the card above pass valuei1 15 2 2 20 4 3 25 6 4 30 8 5 42 10 rank ← 20.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 20.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val15}: {rank20.0:.1f}th percentile")outputValue 15: 20.0th percentilerank ← 40.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 40.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val20)93 print(f"Value {val20}: {rank40.0:.1f}th percentile")outputValue 20: 40.0th percentilerank ← 60.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 60.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val25)93 print(f"Value {val25}: {rank60.0:.1f}th percentile")outputValue 25: 60.0th percentilerank ← 80.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 80.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val30)93 print(f"Value {val30}: {rank80.0:.1f}th percentile")outputValue 30: 80.0th percentilerank ← 100.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 100.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val42)93 print(f"Value {val42}: {rank100.0:.1f}th percentile")outputValue 42: 100.0th percentilenumbers ← [10, 20, 30, 40, 50, 60]
95# Find closest value96print("\nFind closest value:")9798numbers→ [10, 20, 30, 40, 50, 60] = [10, 20, 30, 40, 50, 60]output Find closest value:for target in [15, 25, 35, 5, 65]:
pass 1 of 5118for target15 in [15, 25, 35, 5, 65]:119 closest = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target}: {closest}")All 5 passes — pass 1 is the card above pass targetisorted_list[0]sorted_listsorted_list[-1]1 15 — — — — 2 25 — — — — 3 35 — — — — 4 5 0 10 — — 5 65 6 — [10, 20, 30, 40, 50, 60] 60 i ← 1, before ← 10, after ← 20
pass 1 of 5100def find_closest(sorted_list[10, 20, 30, 40, 50, 60], target15):101 """Find closest value to target"""102 i→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50, 60], target15)103 104 if i == 0:105 return sorted_list[0]106 if i == len(sorted_list):107 return sorted_list[-1]108 109 # Check which is closer110 before→ 10 = sorted_list[i - 1]10111 after→ 20 = sorted_list[i]20All 5 passes — pass 1 is the card above pass targetsorted_list[i - 1]sorted_list[i]sorted_list[0]sorted_list[-1]ibeforeafter1 15 10 20 — — 1 10 20 2 25 20 30 — — 2 20 30 3 35 30 40 — — 3 30 40 4 5 — — 10 — 0 — — 5 65 — — — 60 6 — — else:
pass 1 of 3113if target - before < after - target:114 return before115else:116 return after20All 3 passes — pass 1 is the card above pass after1 20 2 30 3 40 closest ← 20
118for target in [15, 25, 35, 5, 65]:119 closest→ 20 = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target15}: {closest20}")outputClosest to 15: 20closest ← 30
118for target in [15, 25, 35, 5, 65]:119 closest→ 30 = find_closest(numbers[10, 20, 30, 40, 50, 60], target25)120 print(f"Closest to {target25}: {closest30}")outputClosest to 25: 30closest ← 40
118for target in [15, 25, 35, 5, 65]:119 closest→ 40 = find_closest(numbers[10, 20, 30, 40, 50, 60], target35)120 print(f"Closest to {target35}: {closest40}")outputClosest to 35: 40if i == 0:
104if i0 == 0:105 return sorted_list[0]10106if i == len(sorted_list):closest ← 10
118for target in [15, 25, 35, 5, 65]:119 closest→ 10 = find_closest(numbers[10, 20, 30, 40, 50, 60], target5)120 print(f"Closest to {target5}: {closest10}")outputClosest to 5: 10if i == len(sorted_list):
105 return sorted_list[0]106if i6 == len(sorted_list[10, 20, 30, 40, 50, 60]):107 return sorted_list[-1]60closest ← 60
118for target in [15, 25, 35, 5, 65]:119 closest→ 60 = find_closest(numbers[10, 20, 30, 40, 50, 60], target65)120 print(f"Closest to {target65}: {closest60}")outputClosest to 65: 60numbers ← [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
122# Range search123print("\nRange search:")124125numbers→ [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]126127def find_range(sorted_list, low, high):128 """Find all values in range [low, high)"""129 start = bisect.bisect_left(sorted_list, low)130 end = bisect.bisect_left(sorted_list, high)131 return sorted_list[start:end]132133result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result}")output Range search:start ← 2, end ← 6
pass 1 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15, high35):128 """Find all values in range [low, high)"""129 start→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15)130 end→ 6 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high35)131 return sorted_list[start:end][15, 20, 25, 30]result ← [15, 20, 25, 30]
133result→ [15, 20, 25, 30] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result[15, 20, 25, 30]}")135136result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result}")start ← 3, end ← 7
pass 2 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20, high40):128 """Find all values in range [low, high)"""129 start→ 3 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20)130 end→ 7 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high40)131 return sorted_list[start:end][20, 25, 30, 35]result ← [20, 25, 30, 35], numbers ← [-10, -5, 0, 3, 7, 12], target ← -6
136result→ [20, 25, 30, 35] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result[20, 25, 30, 35]}")138139# Custom key function140print("\nCustom key function:")141142# Sort by absolute value143numbers→ [-10, -5, 0, 3, 7, 12] = [-10, -5, 0, 3, 7, 12]144target→ -6 = -6145146# Find where to insert -6 when sorted by absolute value147abs_numbers→ [10, 5, 0, 3, 7, 12] = [abs(x) for x in numbers[-10, -5, 0, 3, 7, 12]]148pos→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(abs_numbers[10, 5, 0, 3, 7, 12], abs(target-6))149150print(f"Original: {numbers[-10, -5, 0, 3, 7, 12]}")151print(f"Sorted by abs: {abs_numbers[10, 5, 0, 3, 7, 12]}")152print(f"Insert {target-6} at position {pos4}")output Custom key function: Original: [-10, -5, 0, 3, 7, 12] Sorted by abs: [10, 5, 0, 3, 7, 12] Insert -6 at position 4
numbers ← [1, 3, 3, 3, 5, 7, 9], value ← 2, left ← 1, right ← 1
1"""bisect module examples"""23import bisect45# bisect_left vs bisect_right6print("bisect_left vs bisect_right:")78numbers→ [1, 3, 3, 3, 5, 7, 9] = [1, 3, 3, 3, 5, 7, 9]9value→ 2 = 21011# Find leftmost position12left→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 3, 3, 3, 5, 7, 9], value2)13print(f"bisect_left({numbers[1, 3, 3, 3, 5, 7, 9]}, {value2}): {left1}")14print(f" Would insert at index {left1} (before existing 3s)")1516# Find rightmost position17right→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 3, 3, 3, 5, 7, 9], value2)18print(f"bisect_right({numbers[1, 3, 3, 3, 5, 7, 9]}, {value2}): {right1}")19print(f" Would insert at index {right1} (after existing 3s)")2021# bisect is alias for bisect_right22regular→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(numbers[1, 3, 3, 3, 5, 7, 9], value2)23print(f"bisect (same as bisect_right): {regular1}")2425# Find insertion point26print("\nFind insertion point:")2728sorted_list→ [10, 20, 30, 40, 50] = [10, 20, 30, 40, 50]outputbisect_left vs bisect_right: bisect_left([1, 3, 3, 3, 5, 7, 9], 2): 1 Would insert at index 1 (before existing 3s) bisect_right([1, 3, 3, 3, 5, 7, 9], 2): 1 Would insert at index 1 (after existing 3s) bisect (same as bisect_right): 1 Find insertion point:pos ← 1
pass 1 of 530for value15 in [15, 25, 35, 5, 60]:31 pos→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50], value15)32 print(f"Insert {value15} at index {pos1}: {sorted_list[:pos][10] + [value] + sorted_list[pos:][20, 30, 40, 50]}")outputInsert 15 at index 1: [10, 15, 20, 30, 40, 50]All 5 passes — pass 1 is the card above pass valuesorted_list[:pos]sorted_list[pos:]pos1 15 [10] [20, 30, 40, 50] 1 2 25 [10, 20] [30, 40, 50] 2 3 35 [10, 20, 30] [40, 50] 3 4 5 [] [10, 20, 30, 40, 50] 0 5 60 [10, 20, 30, 40, 50] [] 5 numbers ← [1, 3, 5, 7, 9, 11, 13]
34# Check if element exists35print("\nCheck if element exists:")3637numbers→ [1, 3, 5, 7, 9, 11, 13] = [1, 3, 5, 7, 9, 11, 13]output Check if element exists:for val in [5, 6, 13, 14]:
pass 1 of 444for val5 in [5, 6, 13, 14]:45 exists = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val} in list: {exists}")All 4 passes — pass 1 is the card above pass val1 5 2 6 3 13 4 14 i ← 2
pass 1 of 439def contains(sorted_list[1, 3, 5, 7, 9, 11, 13], value5):40 """Check if value is in sorted list using binary search"""41 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[1, 3, 5, 7, 9, 11, 13], value5)42 return i2 < len(sorted_list[1, 3, 5, 7, 9, 11, 13]) and sorted_list[i]5 == value5All 4 passes — pass 1 is the card above pass valuesorted_list[i]i1 5 5 2 2 6 7 3 3 13 13 6 4 14 (empty) 7 exists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val5} in list: {existsTrue}")output5 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val6)46 print(f"{val6} in list: {existsFalse}")output6 in list: Falseexists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val13)46 print(f"{val13} in list: {existsTrue}")output13 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val14)46 print(f"{val14} in list: {existsFalse}")output14 in list: Falsenumbers ← [1, 2, 2, 2, 3, 3, 4, 5], value ← 2, start ← 1, end ← 4
48# Find range of values49print("\nFind range of values:")5051numbers→ [1, 2, 2, 2, 3, 3, 4, 5] = [1, 2, 2, 2, 3, 3, 4, 5]52value→ 2 = 25354# Find range of all 2s55start→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)56end→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)5758print(f"Numbers: {numbers[1, 2, 2, 2, 3, 3, 4, 5]}")59print(f"Value {value2} appears at indices [{start1}:{end4})")60print(f"Count: {end4 - start1}")61print(f"Elements: {numbers[start:end][2, 2, 2]}")6263# Grades example64print("\nGrades example:")6566# Grade boundaries67breakpoints→ [60, 70, 80, 90] = [60, 70, 80, 90]68grades→ ['F', 'D', 'C', 'B', 'A'] = ['F', 'D', 'C', 'B', 'A']6970def get_grade(score):71 """Convert score to letter grade"""72 i = bisect.bisect(breakpoints, score)73 return grades[i]7475scores→ [55, 65, 75, 85, 95, 100] = [55, 65, 75, 85, 95, 100]76for score in scores:output Find range of values: Numbers: [1, 2, 2, 2, 3, 3, 4, 5] Count: 3 Elements: [2, 2, 2] Grades example:for score in scores:
pass 1 of 675scores = [55, 65, 75, 85, 95, 100]76for score55 in scores[55, 65, 75, 85, 95, 100]:77 grade = get_grade(score55)78 print(f"Score {score}: {grade}")All 6 passes — pass 1 is the card above pass score1 55 2 65 3 75 4 85 5 95 6 100 i ← 0
pass 1 of 670def get_grade(score55):71 """Convert score to letter grade"""72 i→ 0 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(breakpoints[60, 70, 80, 90], score55)73 return grades[i]FAll 6 passes — pass 1 is the card above pass scoregrades[i]i1 55 F 0 2 65 D 1 3 75 C 2 4 85 B 3 5 95 A 4 6 100 A 4 grade ← F
76for score in scores:77 grade→ F = get_grade(score55)78 print(f"Score {score55}: {gradeF}")outputScore 55: Fgrade ← D
76for score in scores:77 grade→ D = get_grade(score65)78 print(f"Score {score65}: {gradeD}")outputScore 65: Dgrade ← C
76for score in scores:77 grade→ C = get_grade(score75)78 print(f"Score {score75}: {gradeC}")outputScore 75: Cgrade ← B
76for score in scores:77 grade→ B = get_grade(score85)78 print(f"Score {score85}: {gradeB}")outputScore 85: Bgrade ← A
76for score in scores:77 grade→ A = get_grade(score95)78 print(f"Score {score95}: {gradeA}")outputScore 95: Agrade ← A
76for score in scores:77 grade→ A = get_grade(score100)78 print(f"Score {score100}: {gradeA}")outputScore 100: Adata ← [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
80# Percentile calculation81print("\nPercentile calculation:")8283data→ [12, 15, 18, 20, 22, 25, 28, 30, 35, 40] = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]8485def percentile_rank(sorted_data, value):86 """Calculate percentile rank of value"""87 i = bisect.bisect_right(sorted_data, value)88 return (i / len(sorted_data)) * 1008990print(f"Data: {data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40]}")91for val in [15, 20, 25, 30, 42]:output Percentile calculation: Data: [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]for val in [15, 20, 25, 30, 42]:
pass 1 of 590print(f"Data: {data}")91for val15 in [15, 20, 25, 30, 42]:92 rank = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val}: {rank:.1f}th percentile")All 5 passes — pass 1 is the card above pass val1 15 2 20 3 25 4 30 5 42 i ← 2
pass 1 of 585def percentile_rank(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15):86 """Calculate percentile rank of value"""87 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15)88 return (i2 / len(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40])) * 100All 5 passes — pass 1 is the card above pass valuei1 15 2 2 20 4 3 25 6 4 30 8 5 42 10 rank ← 20.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 20.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val15}: {rank20.0:.1f}th percentile")outputValue 15: 20.0th percentilerank ← 40.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 40.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val20)93 print(f"Value {val20}: {rank40.0:.1f}th percentile")outputValue 20: 40.0th percentilerank ← 60.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 60.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val25)93 print(f"Value {val25}: {rank60.0:.1f}th percentile")outputValue 25: 60.0th percentilerank ← 80.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 80.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val30)93 print(f"Value {val30}: {rank80.0:.1f}th percentile")outputValue 30: 80.0th percentilerank ← 100.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 100.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val42)93 print(f"Value {val42}: {rank100.0:.1f}th percentile")outputValue 42: 100.0th percentilenumbers ← [10, 20, 30, 40, 50, 60]
95# Find closest value96print("\nFind closest value:")9798numbers→ [10, 20, 30, 40, 50, 60] = [10, 20, 30, 40, 50, 60]output Find closest value:for target in [15, 25, 35, 5, 65]:
pass 1 of 5118for target15 in [15, 25, 35, 5, 65]:119 closest = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target}: {closest}")All 5 passes — pass 1 is the card above pass targetisorted_list[0]sorted_listsorted_list[-1]1 15 — — — — 2 25 — — — — 3 35 — — — — 4 5 0 10 — — 5 65 6 — [10, 20, 30, 40, 50, 60] 60 i ← 1, before ← 10, after ← 20
pass 1 of 5100def find_closest(sorted_list[10, 20, 30, 40, 50, 60], target15):101 """Find closest value to target"""102 i→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50, 60], target15)103 104 if i == 0:105 return sorted_list[0]106 if i == len(sorted_list):107 return sorted_list[-1]108 109 # Check which is closer110 before→ 10 = sorted_list[i - 1]10111 after→ 20 = sorted_list[i]20All 5 passes — pass 1 is the card above pass targetsorted_list[i - 1]sorted_list[i]sorted_list[0]sorted_list[-1]ibeforeafter1 15 10 20 — — 1 10 20 2 25 20 30 — — 2 20 30 3 35 30 40 — — 3 30 40 4 5 — — 10 — 0 — — 5 65 — — — 60 6 — — else:
pass 1 of 3113if target - before < after - target:114 return before115else:116 return after20All 3 passes — pass 1 is the card above pass after1 20 2 30 3 40 closest ← 20
118for target in [15, 25, 35, 5, 65]:119 closest→ 20 = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target15}: {closest20}")outputClosest to 15: 20closest ← 30
118for target in [15, 25, 35, 5, 65]:119 closest→ 30 = find_closest(numbers[10, 20, 30, 40, 50, 60], target25)120 print(f"Closest to {target25}: {closest30}")outputClosest to 25: 30closest ← 40
118for target in [15, 25, 35, 5, 65]:119 closest→ 40 = find_closest(numbers[10, 20, 30, 40, 50, 60], target35)120 print(f"Closest to {target35}: {closest40}")outputClosest to 35: 40if i == 0:
104if i0 == 0:105 return sorted_list[0]10106if i == len(sorted_list):closest ← 10
118for target in [15, 25, 35, 5, 65]:119 closest→ 10 = find_closest(numbers[10, 20, 30, 40, 50, 60], target5)120 print(f"Closest to {target5}: {closest10}")outputClosest to 5: 10if i == len(sorted_list):
105 return sorted_list[0]106if i6 == len(sorted_list[10, 20, 30, 40, 50, 60]):107 return sorted_list[-1]60closest ← 60
118for target in [15, 25, 35, 5, 65]:119 closest→ 60 = find_closest(numbers[10, 20, 30, 40, 50, 60], target65)120 print(f"Closest to {target65}: {closest60}")outputClosest to 65: 60numbers ← [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
122# Range search123print("\nRange search:")124125numbers→ [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]126127def find_range(sorted_list, low, high):128 """Find all values in range [low, high)"""129 start = bisect.bisect_left(sorted_list, low)130 end = bisect.bisect_left(sorted_list, high)131 return sorted_list[start:end]132133result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result}")output Range search:start ← 2, end ← 6
pass 1 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15, high35):128 """Find all values in range [low, high)"""129 start→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15)130 end→ 6 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high35)131 return sorted_list[start:end][15, 20, 25, 30]result ← [15, 20, 25, 30]
133result→ [15, 20, 25, 30] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result[15, 20, 25, 30]}")135136result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result}")start ← 3, end ← 7
pass 2 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20, high40):128 """Find all values in range [low, high)"""129 start→ 3 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20)130 end→ 7 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high40)131 return sorted_list[start:end][20, 25, 30, 35]result ← [20, 25, 30, 35], numbers ← [-10, -5, 0, 3, 7, 12], target ← -6
136result→ [20, 25, 30, 35] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result[20, 25, 30, 35]}")138139# Custom key function140print("\nCustom key function:")141142# Sort by absolute value143numbers→ [-10, -5, 0, 3, 7, 12] = [-10, -5, 0, 3, 7, 12]144target→ -6 = -6145146# Find where to insert -6 when sorted by absolute value147abs_numbers→ [10, 5, 0, 3, 7, 12] = [abs(x) for x in numbers[-10, -5, 0, 3, 7, 12]]148pos→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(abs_numbers[10, 5, 0, 3, 7, 12], abs(target-6))149150print(f"Original: {numbers[-10, -5, 0, 3, 7, 12]}")151print(f"Sorted by abs: {abs_numbers[10, 5, 0, 3, 7, 12]}")152print(f"Insert {target-6} at position {pos4}")output Custom key function: Original: [-10, -5, 0, 3, 7, 12] Sorted by abs: [10, 5, 0, 3, 7, 12] Insert -6 at position 4
numbers ← [1, 3, 3, 3, 5, 7, 9], value ← 5, left ← 4, right ← 5
1"""bisect module examples"""23import bisect45# bisect_left vs bisect_right6print("bisect_left vs bisect_right:")78numbers→ [1, 3, 3, 3, 5, 7, 9] = [1, 3, 3, 3, 5, 7, 9]9value→ 5 = 51011# Find leftmost position12left→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 3, 3, 3, 5, 7, 9], value5)13print(f"bisect_left({numbers[1, 3, 3, 3, 5, 7, 9]}, {value5}): {left4}")14print(f" Would insert at index {left4} (before existing 3s)")1516# Find rightmost position17right→ 5 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 3, 3, 3, 5, 7, 9], value5)18print(f"bisect_right({numbers[1, 3, 3, 3, 5, 7, 9]}, {value5}): {right5}")19print(f" Would insert at index {right5} (after existing 3s)")2021# bisect is alias for bisect_right22regular→ 5 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(numbers[1, 3, 3, 3, 5, 7, 9], value5)23print(f"bisect (same as bisect_right): {regular5}")2425# Find insertion point26print("\nFind insertion point:")2728sorted_list→ [10, 20, 30, 40, 50] = [10, 20, 30, 40, 50]outputbisect_left vs bisect_right: bisect_left([1, 3, 3, 3, 5, 7, 9], 5): 4 Would insert at index 4 (before existing 3s) bisect_right([1, 3, 3, 3, 5, 7, 9], 5): 5 Would insert at index 5 (after existing 3s) bisect (same as bisect_right): 5 Find insertion point:pos ← 1
pass 1 of 530for value15 in [15, 25, 35, 5, 60]:31 pos→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50], value15)32 print(f"Insert {value15} at index {pos1}: {sorted_list[:pos][10] + [value] + sorted_list[pos:][20, 30, 40, 50]}")outputInsert 15 at index 1: [10, 15, 20, 30, 40, 50]All 5 passes — pass 1 is the card above pass valuesorted_list[:pos]sorted_list[pos:]pos1 15 [10] [20, 30, 40, 50] 1 2 25 [10, 20] [30, 40, 50] 2 3 35 [10, 20, 30] [40, 50] 3 4 5 [] [10, 20, 30, 40, 50] 0 5 60 [10, 20, 30, 40, 50] [] 5 numbers ← [1, 3, 5, 7, 9, 11, 13]
34# Check if element exists35print("\nCheck if element exists:")3637numbers→ [1, 3, 5, 7, 9, 11, 13] = [1, 3, 5, 7, 9, 11, 13]output Check if element exists:for val in [5, 6, 13, 14]:
pass 1 of 444for val5 in [5, 6, 13, 14]:45 exists = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val} in list: {exists}")All 4 passes — pass 1 is the card above pass val1 5 2 6 3 13 4 14 i ← 2
pass 1 of 439def contains(sorted_list[1, 3, 5, 7, 9, 11, 13], value5):40 """Check if value is in sorted list using binary search"""41 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[1, 3, 5, 7, 9, 11, 13], value5)42 return i2 < len(sorted_list[1, 3, 5, 7, 9, 11, 13]) and sorted_list[i]5 == value5All 4 passes — pass 1 is the card above pass valuesorted_list[i]i1 5 5 2 2 6 7 3 3 13 13 6 4 14 (empty) 7 exists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val5)46 print(f"{val5} in list: {existsTrue}")output5 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val6)46 print(f"{val6} in list: {existsFalse}")output6 in list: Falseexists ← True
44for val in [5, 6, 13, 14]:45 exists→ True = contains(numbers[1, 3, 5, 7, 9, 11, 13], val13)46 print(f"{val13} in list: {existsTrue}")output13 in list: Trueexists ← False
44for val in [5, 6, 13, 14]:45 exists→ False = contains(numbers[1, 3, 5, 7, 9, 11, 13], val14)46 print(f"{val14} in list: {existsFalse}")output14 in list: Falsenumbers ← [1, 2, 2, 2, 3, 3, 4, 5], value ← 2, start ← 1, end ← 4
48# Find range of values49print("\nFind range of values:")5051numbers→ [1, 2, 2, 2, 3, 3, 4, 5] = [1, 2, 2, 2, 3, 3, 4, 5]52value→ 2 = 25354# Find range of all 2s55start→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)56end→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(numbers[1, 2, 2, 2, 3, 3, 4, 5], value2)5758print(f"Numbers: {numbers[1, 2, 2, 2, 3, 3, 4, 5]}")59print(f"Value {value2} appears at indices [{start1}:{end4})")60print(f"Count: {end4 - start1}")61print(f"Elements: {numbers[start:end][2, 2, 2]}")6263# Grades example64print("\nGrades example:")6566# Grade boundaries67breakpoints→ [60, 70, 80, 90] = [60, 70, 80, 90]68grades→ ['F', 'D', 'C', 'B', 'A'] = ['F', 'D', 'C', 'B', 'A']6970def get_grade(score):71 """Convert score to letter grade"""72 i = bisect.bisect(breakpoints, score)73 return grades[i]7475scores→ [55, 65, 75, 85, 95, 100] = [55, 65, 75, 85, 95, 100]76for score in scores:output Find range of values: Numbers: [1, 2, 2, 2, 3, 3, 4, 5] Count: 3 Elements: [2, 2, 2] Grades example:for score in scores:
pass 1 of 675scores = [55, 65, 75, 85, 95, 100]76for score55 in scores[55, 65, 75, 85, 95, 100]:77 grade = get_grade(score55)78 print(f"Score {score}: {grade}")All 6 passes — pass 1 is the card above pass score1 55 2 65 3 75 4 85 5 95 6 100 i ← 0
pass 1 of 670def get_grade(score55):71 """Convert score to letter grade"""72 i→ 0 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect(breakpoints[60, 70, 80, 90], score55)73 return grades[i]FAll 6 passes — pass 1 is the card above pass scoregrades[i]i1 55 F 0 2 65 D 1 3 75 C 2 4 85 B 3 5 95 A 4 6 100 A 4 grade ← F
76for score in scores:77 grade→ F = get_grade(score55)78 print(f"Score {score55}: {gradeF}")outputScore 55: Fgrade ← D
76for score in scores:77 grade→ D = get_grade(score65)78 print(f"Score {score65}: {gradeD}")outputScore 65: Dgrade ← C
76for score in scores:77 grade→ C = get_grade(score75)78 print(f"Score {score75}: {gradeC}")outputScore 75: Cgrade ← B
76for score in scores:77 grade→ B = get_grade(score85)78 print(f"Score {score85}: {gradeB}")outputScore 85: Bgrade ← A
76for score in scores:77 grade→ A = get_grade(score95)78 print(f"Score {score95}: {gradeA}")outputScore 95: Agrade ← A
76for score in scores:77 grade→ A = get_grade(score100)78 print(f"Score {score100}: {gradeA}")outputScore 100: Adata ← [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]
80# Percentile calculation81print("\nPercentile calculation:")8283data→ [12, 15, 18, 20, 22, 25, 28, 30, 35, 40] = [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]8485def percentile_rank(sorted_data, value):86 """Calculate percentile rank of value"""87 i = bisect.bisect_right(sorted_data, value)88 return (i / len(sorted_data)) * 1008990print(f"Data: {data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40]}")91for val in [15, 20, 25, 30, 42]:output Percentile calculation: Data: [12, 15, 18, 20, 22, 25, 28, 30, 35, 40]for val in [15, 20, 25, 30, 42]:
pass 1 of 590print(f"Data: {data}")91for val15 in [15, 20, 25, 30, 42]:92 rank = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val}: {rank:.1f}th percentile")All 5 passes — pass 1 is the card above pass val1 15 2 20 3 25 4 30 5 42 i ← 2
pass 1 of 585def percentile_rank(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15):86 """Calculate percentile rank of value"""87 i→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_right(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], value15)88 return (i2 / len(sorted_data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40])) * 100All 5 passes — pass 1 is the card above pass valuei1 15 2 2 20 4 3 25 6 4 30 8 5 42 10 rank ← 20.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 20.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val15)93 print(f"Value {val15}: {rank20.0:.1f}th percentile")outputValue 15: 20.0th percentilerank ← 40.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 40.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val20)93 print(f"Value {val20}: {rank40.0:.1f}th percentile")outputValue 20: 40.0th percentilerank ← 60.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 60.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val25)93 print(f"Value {val25}: {rank60.0:.1f}th percentile")outputValue 25: 60.0th percentilerank ← 80.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 80.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val30)93 print(f"Value {val30}: {rank80.0:.1f}th percentile")outputValue 30: 80.0th percentilerank ← 100.0
91for val in [15, 20, 25, 30, 42]:92 rank→ 100.0 = percentile_rank(data[12, 15, 18, 20, 22, 25, 28, 30, 35, 40], val42)93 print(f"Value {val42}: {rank100.0:.1f}th percentile")outputValue 42: 100.0th percentilenumbers ← [10, 20, 30, 40, 50, 60]
95# Find closest value96print("\nFind closest value:")9798numbers→ [10, 20, 30, 40, 50, 60] = [10, 20, 30, 40, 50, 60]output Find closest value:for target in [15, 25, 35, 5, 65]:
pass 1 of 5118for target15 in [15, 25, 35, 5, 65]:119 closest = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target}: {closest}")All 5 passes — pass 1 is the card above pass targetisorted_list[0]sorted_listsorted_list[-1]1 15 — — — — 2 25 — — — — 3 35 — — — — 4 5 0 10 — — 5 65 6 — [10, 20, 30, 40, 50, 60] 60 i ← 1, before ← 10, after ← 20
pass 1 of 5100def find_closest(sorted_list[10, 20, 30, 40, 50, 60], target15):101 """Find closest value to target"""102 i→ 1 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[10, 20, 30, 40, 50, 60], target15)103 104 if i == 0:105 return sorted_list[0]106 if i == len(sorted_list):107 return sorted_list[-1]108 109 # Check which is closer110 before→ 10 = sorted_list[i - 1]10111 after→ 20 = sorted_list[i]20All 5 passes — pass 1 is the card above pass targetsorted_list[i - 1]sorted_list[i]sorted_list[0]sorted_list[-1]ibeforeafter1 15 10 20 — — 1 10 20 2 25 20 30 — — 2 20 30 3 35 30 40 — — 3 30 40 4 5 — — 10 — 0 — — 5 65 — — — 60 6 — — else:
pass 1 of 3113if target - before < after - target:114 return before115else:116 return after20All 3 passes — pass 1 is the card above pass after1 20 2 30 3 40 closest ← 20
118for target in [15, 25, 35, 5, 65]:119 closest→ 20 = find_closest(numbers[10, 20, 30, 40, 50, 60], target15)120 print(f"Closest to {target15}: {closest20}")outputClosest to 15: 20closest ← 30
118for target in [15, 25, 35, 5, 65]:119 closest→ 30 = find_closest(numbers[10, 20, 30, 40, 50, 60], target25)120 print(f"Closest to {target25}: {closest30}")outputClosest to 25: 30closest ← 40
118for target in [15, 25, 35, 5, 65]:119 closest→ 40 = find_closest(numbers[10, 20, 30, 40, 50, 60], target35)120 print(f"Closest to {target35}: {closest40}")outputClosest to 35: 40if i == 0:
104if i0 == 0:105 return sorted_list[0]10106if i == len(sorted_list):closest ← 10
118for target in [15, 25, 35, 5, 65]:119 closest→ 10 = find_closest(numbers[10, 20, 30, 40, 50, 60], target5)120 print(f"Closest to {target5}: {closest10}")outputClosest to 5: 10if i == len(sorted_list):
105 return sorted_list[0]106if i6 == len(sorted_list[10, 20, 30, 40, 50, 60]):107 return sorted_list[-1]60closest ← 60
118for target in [15, 25, 35, 5, 65]:119 closest→ 60 = find_closest(numbers[10, 20, 30, 40, 50, 60], target65)120 print(f"Closest to {target65}: {closest60}")outputClosest to 65: 60numbers ← [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
122# Range search123print("\nRange search:")124125numbers→ [5, 10, 15, 20, 25, 30, 35, 40, 45, 50] = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]126127def find_range(sorted_list, low, high):128 """Find all values in range [low, high)"""129 start = bisect.bisect_left(sorted_list, low)130 end = bisect.bisect_left(sorted_list, high)131 return sorted_list[start:end]132133result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result}")output Range search:start ← 2, end ← 6
pass 1 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15, high35):128 """Find all values in range [low, high)"""129 start→ 2 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low15)130 end→ 6 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high35)131 return sorted_list[start:end][15, 20, 25, 30]result ← [15, 20, 25, 30]
133result→ [15, 20, 25, 30] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 15, 35)134print(f"Values in [15, 35): {result[15, 20, 25, 30]}")135136result = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result}")start ← 3, end ← 7
pass 2 of 2127def find_range(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20, high40):128 """Find all values in range [low, high)"""129 start→ 3 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], low20)130 end→ 7 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(sorted_list[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], high40)131 return sorted_list[start:end][20, 25, 30, 35]result ← [20, 25, 30, 35], numbers ← [-10, -5, 0, 3, 7, 12], target ← -6
136result→ [20, 25, 30, 35] = find_range(numbers[5, 10, 15, 20, 25, 30, 35, 40, 45, 50], 20, 40)137print(f"Values in [20, 40): {result[20, 25, 30, 35]}")138139# Custom key function140print("\nCustom key function:")141142# Sort by absolute value143numbers→ [-10, -5, 0, 3, 7, 12] = [-10, -5, 0, 3, 7, 12]144target→ -6 = -6145146# Find where to insert -6 when sorted by absolute value147abs_numbers→ [10, 5, 0, 3, 7, 12] = [abs(x) for x in numbers[-10, -5, 0, 3, 7, 12]]148pos→ 4 = bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.bisect_left(abs_numbers[10, 5, 0, 3, 7, 12], abs(target-6))149150print(f"Original: {numbers[-10, -5, 0, 3, 7, 12]}")151print(f"Sorted by abs: {abs_numbers[10, 5, 0, 3, 7, 12]}")152print(f"Insert {target-6} at position {pos4}")output Custom key function: Original: [-10, -5, 0, 3, 7, 12] Sorted by abs: [10, 5, 0, 3, 7, 12] Insert -6 at position 4
bisect_left vs bisect_right
bisect_left returns the leftmost position for equal values, bisect_right returns the rightmost - matters when duplicates exist.
Insort Operations
Insert while maintaining sort order:
insort.py
Replay: real traced execution (multi-file project)
"""bisect.insort examples"""
import bisect
# Basic insort
print("Basic insort:")
numbers = [1, 3, 5, 7, 9]
print(f"Original: {numbers}")
# Insert maintaining order
bisect.insort(numbers, 4)
print(f"After insort(4): {numbers}")
bisect.insort(numbers, 6)
print(f"After insort(6): {numbers}")
bisect.insort(numbers, 0)
print(f"After insort(0): {numbers}")
# insort_left vs insort_right
print("\ninsort_left vs insort_right:")
# insort_left
left_list = [1, 3, 3, 3, 5]
bisect.insort_left(left_list, 3)
print(f"insort_left(3): {left_list}")
print(" Inserts before existing 3s")
# insort_right (default)
right_list = [1, 3, 3, 3, 5]
bisect.insort_right(right_list, 3)
print(f"insort_right(3): {right_list}")
print(" Inserts after existing 3s")
# Build sorted list
print("\nBuild sorted list:")
unsorted = [5, 2, 8, 1, 9, 3, 7]
sorted_list = []
print(f"Unsorted: {unsorted}")
for num in unsorted:
bisect.insort(sorted_list, num)
print(f" Insert {num}: {sorted_list}")
print(f"Final sorted: {sorted_list}")
# Maintain top-N sorted
print("\nMaintain top-N sorted:")
def keep_top_n(sorted_list, value, n):
"""Keep only top N smallest values"""
bisect.insort(sorted_list, value)
return sorted_list[:n]
top_5 = []
values = [30, 10, 50, 20, 40, 15, 25, 35]
print("Maintaining top 5 smallest:")
for val in values:
top_5 = keep_top_n(top_5, val, 5)
print(f" Insert {val}: {top_5}")
# Sorted event log
print("\nSorted event log:")
class Event:
def __init__(self, time, message):
self.time = time
self.message = message
def __lt__(self, other):
return self.time < other.time
def __repr__(self):
return f"Event({self.time}, '{self.message}')"
events = []
# Insert events in random order, kept sorted by time
bisect.insort(events, Event(10, "Start"))
bisect.insort(events, Event(5, "Init"))
bisect.insort(events, Event(15, "Process"))
bisect.insort(events, Event(3, "Load"))
bisect.insort(events, Event(20, "Finish"))
print("Events (auto-sorted by time):")
for event in events:
print(f" {event}")
# Score insertion
print("\nScore insertion:")
class Player:
def __init__(self, name, score):
self.name = name
self.score = score
def __lt__(self, other):
# Higher score is "less than" for descending order
return self.score > other.score
def __repr__(self):
return f"{self.name}: {self.score}"
leaderboard = []
players = [
Player("Alice", 850),
Player("Bob", 920),
Player("Charlie", 780),
Player("David", 900)
]
for player in players:
bisect.insort(leaderboard, player)
print(f"After {player.name}:")
for i, p in enumerate(leaderboard, 1):
print(f" #{i}: {p}")
print()
# Merge sorted lists
print("\nMerge sorted lists:")
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]
merged = list(list1) # Copy list1
for num in list2:
bisect.insort(merged, num)
print(f"List 1: {list1}")
print(f"List 2: {list2}")
print(f"Merged: {merged}")
# Custom ordering
print("\nCustom ordering:")
# Sort strings by length, then alphabetically
class CustomStr:
def __init__(self, s):
self.s = s
def __lt__(self, other):
if len(self.s) != len(other.s):
return len(self.s) < len(other.s)
return self.s < other.s
def __repr__(self):
return self.s
words = []
for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:
bisect.insort(words, CustomStr(word))
print("Words sorted by length, then alpha:")
print([str(w) for w in words])
# Performance guidance
print("\nPerformance guidance:")
# insort approach
sorted_insort = []
data = list(range(80, 0, -1))
for num in data:
bisect.insort(sorted_insort, num)
# sort approach
sorted_sort = sorted(data)
print(f"Both approaches agree: {sorted_insort == sorted_sort}")
print("Note: sorted() is faster for bulk operations")
print(" insort is better for incremental additions")
numbers ← [1, 3, 5, 7, 9], left_list ← [1, 3, 3, 3, 5], right_list ← [1, 3, 3, 3, 5]
1"""bisect.insort examples"""23import bisect45# Basic insort6print("Basic insort:")78numbers→ [1, 3, 5, 7, 9] = [1, 3, 5, 7, 9]9print(f"Original: {numbers[1, 3, 5, 7, 9]}")1011# Insert maintaining order12bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(numbers→ [1, 3, 4, 5, 7, 9], 4)13print(f"After insort(4): {numbers[1, 3, 4, 5, 7, 9]}")1415bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(numbers→ [1, 3, 4, 5, 6, 7, 9], 6)16print(f"After insort(6): {numbers[1, 3, 4, 5, 6, 7, 9]}")1718bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(numbers→ [0, 1, 3, 4, 5, 6, 7, 9], 0)19print(f"After insort(0): {numbers[0, 1, 3, 4, 5, 6, 7, 9]}")2021# insort_left vs insort_right22print("\ninsort_left vs insort_right:")2324# insort_left25left_list→ [1, 3, 3, 3, 5] = [1, 3, 3, 3, 5]26bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort_left(left_list→ [1, 3, 3, 3, 3, 5], 3)27print(f"insort_left(3): {left_list[1, 3, 3, 3, 3, 5]}")28print(" Inserts before existing 3s")2930# insort_right (default)31right_list→ [1, 3, 3, 3, 5] = [1, 3, 3, 3, 5]32bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort_right(right_list→ [1, 3, 3, 3, 3, 5], 3)33print(f"insort_right(3): {right_list[1, 3, 3, 3, 3, 5]}")34print(" Inserts after existing 3s")3536# Build sorted list37print("\nBuild sorted list:")3839unsorted→ [5, 2, 8, 1, 9, 3, 7] = [5, 2, 8, 1, 9, 3, 7]40sorted_list→ [] = []4142print(f"Unsorted: {unsorted[5, 2, 8, 1, 9, 3, 7]}")outputBasic insort: Original: [1, 3, 5, 7, 9] After insort(4): [1, 3, 4, 5, 7, 9] After insort(6): [1, 3, 4, 5, 6, 7, 9] After insort(0): [0, 1, 3, 4, 5, 6, 7, 9] insort_left vs insort_right: insort_left(3): [1, 3, 3, 3, 3, 5] Inserts before existing 3s insort_right(3): [1, 3, 3, 3, 3, 5] Inserts after existing 3s Build sorted list: Unsorted: [5, 2, 8, 1, 9, 3, 7]sorted_list ← [5]
pass 1 of 744for num5 in unsorted[5, 2, 8, 1, 9, 3, 7]:45 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(sorted_list→ [5], num5)46 print(f" Insert {num5}: {sorted_list[5]}")output Insert 5: [5]All 7 passes — pass 1 is the card above pass numsorted_list1 5 [] → [5] 2 2 [5] → [2, 5] 3 8 [2, 5] → [2, 5, 8] 4 1 [2, 5, 8] → [1, 2, 5, 8] 5 9 [1, 2, 5, 8] → [1, 2, 5, 8, 9] 6 3 [1, 2, 5, 8, 9] → [1, 2, 3, 5, 8, 9] 7 7 [1, 2, 3, 5, 8, 9] → [1, 2, 3, 5, 7, 8, 9] top_5 ← [], values ← [30, 10, 50, 20, 40, 15, 25, 35]
48print(f"Final sorted: {sorted_list[1, 2, 3, 5, 7, 8, 9]}")4950# Maintain top-N sorted51print("\nMaintain top-N sorted:")5253def keep_top_n(sorted_list, value, n):54 """Keep only top N smallest values"""55 bisect.insort(sorted_list, value)56 return sorted_list[:n]5758top_5→ [] = []59values→ [30, 10, 50, 20, 40, 15, 25, 35] = [30, 10, 50, 20, 40, 15, 25, 35]6061print("Maintaining top 5 smallest:")62for val in values:outputFinal sorted: [1, 2, 3, 5, 7, 8, 9] Maintain top-N sorted: Maintaining top 5 smallest:for val in values:
pass 1 of 861print("Maintaining top 5 smallest:")62for val30 in values[30, 10, 50, 20, 40, 15, 25, 35]:63 top_5 = keep_top_n(top_5[], val30, 5)64 print(f" Insert {val}: {top_5}")All 8 passes — pass 1 is the card above pass valtop_51 30 [] 2 10 [30] 3 50 [10, 30] 4 20 [10, 30, 50] 5 40 [10, 20, 30, 50] 6 15 [10, 20, 30, 40, 50] 7 25 [10, 15, 20, 30, 40] 8 35 [10, 15, 20, 25, 30] sorted_list ← [30]
pass 1 of 853def keep_top_n(sorted_list[], value30, n5):54 """Keep only top N smallest values"""55 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(sorted_list→ [30], value30)56 return sorted_list[:n][30]All 8 passes — pass 1 is the card above pass valuesorted_list[:n]sorted_list1 30 [30] [] → [30] 2 10 [10, 30] [30] → [10, 30] 3 50 [10, 30, 50] [10, 30] → [10, 30, 50] 4 20 [10, 20, 30, 50] [10, 30, 50] → [10, 20, 30, 50] 5 40 [10, 20, 30, 40, 50] [10, 20, 30, 50] → [10, 20, 30, 40, 50] 6 15 [10, 15, 20, 30, 40] [10, 20, 30, 40, 50] → [10, 15, 20, 30, 40, 50] 7 25 [10, 15, 20, 25, 30] [10, 15, 20, 30, 40] → [10, 15, 20, 25, 30, 40] 8 35 [10, 15, 20, 25, 30] [10, 15, 20, 25, 30] → [10, 15, 20, 25, 30, 35] top_5 ← [30]
62for val in values:63 top_5→ [30] = keep_top_n(top_5, val30, 5)64 print(f" Insert {val30}: {top_5[30]}")output Insert 30: [30]top_5 ← [10, 30]
62for val in values:63 top_5→ [10, 30] = keep_top_n(top_5, val10, 5)64 print(f" Insert {val10}: {top_5[10, 30]}")output Insert 10: [10, 30]top_5 ← [10, 30, 50]
62for val in values:63 top_5→ [10, 30, 50] = keep_top_n(top_5, val50, 5)64 print(f" Insert {val50}: {top_5[10, 30, 50]}")output Insert 50: [10, 30, 50]top_5 ← [10, 20, 30, 50]
62for val in values:63 top_5→ [10, 20, 30, 50] = keep_top_n(top_5, val20, 5)64 print(f" Insert {val20}: {top_5[10, 20, 30, 50]}")output Insert 20: [10, 20, 30, 50]top_5 ← [10, 20, 30, 40, 50]
62for val in values:63 top_5→ [10, 20, 30, 40, 50] = keep_top_n(top_5, val40, 5)64 print(f" Insert {val40}: {top_5[10, 20, 30, 40, 50]}")output Insert 40: [10, 20, 30, 40, 50]top_5 ← [10, 15, 20, 30, 40]
62for val in values:63 top_5→ [10, 15, 20, 30, 40] = keep_top_n(top_5, val15, 5)64 print(f" Insert {val15}: {top_5[10, 15, 20, 30, 40]}")output Insert 15: [10, 15, 20, 30, 40]top_5 ← [10, 15, 20, 25, 30]
62for val in values:63 top_5→ [10, 15, 20, 25, 30] = keep_top_n(top_5, val25, 5)64 print(f" Insert {val25}: {top_5[10, 15, 20, 25, 30]}")output Insert 25: [10, 15, 20, 25, 30]top_5 ← [10, 15, 20, 25, 30]
62for val in values:63 top_5→ [10, 15, 20, 25, 30] = keep_top_n(top_5, val35, 5)64 print(f" Insert {val35}: {top_5[10, 15, 20, 25, 30]}")output Insert 35: [10, 15, 20, 25, 30]events ← []
66# Sorted event log67print("\nSorted event log:")6869class Event:70 def __init__(self, time, message):71 self.time = time72 self.message = message73 74 def __lt__(self, other):75 return self.time < other.time76 77 def __repr__(self):78 return f"Event({self.time}, '{self.message}')"7980events→ [] = []8182# Insert events in random order, kept sorted by time83bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events[], Event(10, "Start"))84bisect.insort(events, Event(5, "Init"))output Sorted event log:self.time ← 10, self.message ← Start
pass 1 of 569class Event:70 def __init__(self(empty), time10, messageStart):71 self.time→ 10 = time1072 self.message→ Start = messageStartAll 5 passes — pass 1 is the card above pass timemessageself.timeself.message1 10 Start 10 Start 2 5 Init 5 Init 3 15 Process 15 Process 4 3 Load 3 Load 5 20 Finish 20 Finish events ← [Event(10, 'Start')]
82# Insert events in random order, kept sorted by time83bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events→ [Event(10, 'Start')], Event(10, "Start"))84bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events[Event(10, 'Start')], Event(5, "Init"))85bisect.insort(events, Event(15, "Process"))def __lt__(self, other):
pass 1 of 674def __lt__(selfEvent(5, 'Init'), otherEvent(10, 'Start')):75 return self.time5 < other.time10All 6 passes — pass 1 is the card above pass selfotherself.timeother.time1 Event(5, 'Init') Event(10, 'Start') 5 10 2 Event(15, 'Process') Event(10, 'Start') 15 10 3 Event(3, 'Load') Event(10, 'Start') 3 10 4 Event(3, 'Load') Event(5, 'Init') 3 5 5 Event(20, 'Finish') Event(10, 'Start') 20 10 6 Event(20, 'Finish') Event(15, 'Process') 20 15 events ← [Event(5, 'Init'), Event(10, 'Start')]
83bisect.insort(events, Event(10, "Start"))84bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events→ [Event(5, 'Init'), Event(10, 'Start')], Event(5, "Init"))85bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events[Event(5, 'Init'), Event(10, 'Start')], Event(15, "Process"))86bisect.insort(events, Event(3, "Load"))events ← [Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')]
84bisect.insort(events, Event(5, "Init"))85bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events→ [Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')], Event(15, "Process"))86bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events[Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')], Event(3, "Load"))87bisect.insort(events, Event(20, "Finish"))events ← [Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')]
85bisect.insort(events, Event(15, "Process"))86bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events→ [Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')], Event(3, "Load"))87bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events[Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process')], Event(20, "Finish"))events ← [Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process'), Event(20, 'Finish')]
86bisect.insort(events, Event(3, "Load"))87bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(events→ [Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process'), Event(20, 'Finish')], Event(20, "Finish"))8889print("Events (auto-sorted by time):")90for event in events:outputEvents (auto-sorted by time):for event in events:
pass 1 of 589print("Events (auto-sorted by time):")90for eventEvent(3, 'Load') in events[Event(3, 'Load'), Event(5, 'Init'), Event(10, 'Start'), Event(15, 'Process'), Event(20, 'Finish')]:91 print(f" {eventEvent(3, 'Load')}")output Event(3, 'Load')All 5 passes — pass 1 is the card above pass event1 Event(3, 'Load') 2 Event(5, 'Init') 3 Event(10, 'Start') 4 Event(15, 'Process') 5 Event(20, 'Finish') leaderboard ← []
93# Score insertion94print("\nScore insertion:")9596class Player:97 def __init__(self, name, score):98 self.name = name99 self.score = score100 101 def __lt__(self, other):102 # Higher score is "less than" for descending order103 return self.score > other.score104 105 def __repr__(self):106 return f"{self.name}: {self.score}"107108leaderboard→ [] = []109110players = [111 Player("Alice", 850),112 Player("Bob", 920),113 Player("Charlie", 780),114 Player("David", 900)115]output Score insertion:self.name ← Alice, self.score ← 850
pass 1 of 496class Player:97 def __init__(self(empty), nameAlice, score850):98 self.name→ Alice = nameAlice99 self.score→ 850 = score850All 4 passes — pass 1 is the card above pass namescoreself.nameself.score1 Alice 850 Alice 850 2 Bob 920 Bob 920 3 Charlie 780 Charlie 780 4 David 900 David 900 players ← [Alice: 850, Bob: 920, Charlie: 780, David: 900]
110players→ [Alice: 850, Bob: 920, Charlie: 780, David: 900] = [111 Player("Alice", 850),112 Player("Bob", 920),113 Player("Charlie", 780),114 Player("David", 900)115]leaderboard ← [Alice: 850]
pass 1 of 4117for playerAlice: 850 in players[Alice: 850, Bob: 920, Charlie: 780, David: 900]:118 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(leaderboard→ [Alice: 850], playerAlice: 850)119 print(f"After {player.nameAlice}:")120 for i, p in enumerate(leaderboard, 1):outputAfter Alice:All 4 passes — pass 1 is the card above pass playerplayer.nameleaderboard1 Alice: 850 Alice [] → [Alice: 850] 2 Bob: 920 — [Alice: 850] 3 Charlie: 780 — [Bob: 920, Alice: 850] 4 David: 900 — [Bob: 920, Alice: 850, Charlie: 780] for i, p in enumerate(leaderboard, 1):
pass 1 of 10119print(f"After {player.name}:")120for i1, pAlice: 850 in enumerate(leaderboard[Alice: 850], 1):121 print(f" #{i1}: {pAlice: 850}")122print()output #1: Alice: 850All 10 passes — pass 1 is the card above pass ipleaderboard1 1 Alice: 850 [Alice: 850] 2 1 Bob: 920 [Bob: 920, Alice: 850] 3 2 Alice: 850 [Bob: 920, Alice: 850] 4 1 Bob: 920 [Bob: 920, Alice: 850, Charlie: 780] 5 2 Alice: 850 [Bob: 920, Alice: 850, Charlie: 780] 6 3 Charlie: 780 [Bob: 920, Alice: 850, Charlie: 780] 7 1 Bob: 920 [Bob: 920, David: 900, Alice: 850, Charlie: 780] 8 2 David: 900 [Bob: 920, David: 900, Alice: 850, Charlie: 780] 9 3 Alice: 850 [Bob: 920, David: 900, Alice: 850, Charlie: 780] 10 4 Charlie: 780 [Bob: 920, David: 900, Alice: 850, Charlie: 780] print()
121 print(f" #{i}: {p}")122print()def __lt__(self, other): # Higher score is "less than" for des…
pass 1 of 4101def __lt__(selfBob: 920, otherAlice: 850):102 # Higher score is "less than" for descending order103 return self.score920 > other.score850All 4 passes — pass 1 is the card above pass selfotherself.scoreother.score1 Bob: 920 Alice: 850 920 850 2 Charlie: 780 Alice: 850 780 850 3 David: 900 Alice: 850 900 850 4 David: 900 Bob: 920 900 920 leaderboard ← [Bob: 920, Alice: 850]
117for player in players:118 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(leaderboard→ [Bob: 920, Alice: 850], playerBob: 920)119 print(f"After {player.nameBob}:")120 for i, p in enumerate(leaderboard, 1):outputAfter Bob:print()
121 print(f" #{i}: {p}")122print()leaderboard ← [Bob: 920, Alice: 850, Charlie: 780]
117for player in players:118 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(leaderboard→ [Bob: 920, Alice: 850, Charlie: 780], playerCharlie: 780)119 print(f"After {player.nameCharlie}:")120 for i, p in enumerate(leaderboard, 1):outputAfter Charlie:print()
121 print(f" #{i}: {p}")122print()leaderboard ← [Bob: 920, David: 900, Alice: 850, Charlie: 780]
117for player in players:118 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(leaderboard→ [Bob: 920, David: 900, Alice: 850, Charlie: 780], playerDavid: 900)119 print(f"After {player.nameDavid}:")120 for i, p in enumerate(leaderboard, 1):outputAfter David:print()
121 print(f" #{i}: {p}")122print()list1 ← [1, 3, 5, 7], list2 ← [2, 4, 6, 8], merged ← [1, 3, 5, 7]
124# Merge sorted lists125print("\nMerge sorted lists:")126127list1→ [1, 3, 5, 7] = [1, 3, 5, 7]128list2→ [2, 4, 6, 8] = [2, 4, 6, 8]129130merged→ [1, 3, 5, 7] = list(list1[1, 3, 5, 7]) # Copy list1131for num in list2:output Merge sorted lists:merged ← [1, 2, 3, 5, 7]
pass 1 of 4130merged = list(list1) # Copy list1131for num2 in list2[2, 4, 6, 8]:132 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(merged→ [1, 2, 3, 5, 7], num2)All 4 passes — pass 1 is the card above pass nummerged1 2 [1, 3, 5, 7] → [1, 2, 3, 5, 7] 2 4 [1, 2, 3, 5, 7] → [1, 2, 3, 4, 5, 7] 3 6 [1, 2, 3, 4, 5, 7] → [1, 2, 3, 4, 5, 6, 7] 4 8 [1, 2, 3, 4, 5, 6, 7] → [1, 2, 3, 4, 5, 6, 7, 8] words ← []
134print(f"List 1: {list1[1, 3, 5, 7]}")135print(f"List 2: {list2[2, 4, 6, 8]}")136print(f"Merged: {merged[1, 2, 3, 4, 5, 6, 7, 8]}")137138# Custom ordering139print("\nCustom ordering:")140141# Sort strings by length, then alphabetically142class CustomStr:143 def __init__(self, s):144 self.s = s145 146 def __lt__(self, other):147 if len(self.s) != len(other.s):148 return len(self.s) < len(other.s)149 return self.s < other.s150 151 def __repr__(self):152 return self.s153154words→ [] = []155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:outputList 1: [1, 3, 5, 7] List 2: [2, 4, 6, 8] Merged: [1, 2, 3, 4, 5, 6, 7, 8] Custom ordering:for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:
pass 1 of 6154words = []155for wordapple in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words[], CustomStr(wordapple))All 6 passes — pass 1 is the card above pass wordwords1 apple [] 2 pie [apple] 3 banana [pie, apple] 4 kiwi [pie, apple, banana] 5 a [pie, kiwi, apple, banana] 6 at [a, pie, kiwi, apple, banana] self.s ← apple
pass 1 of 6142class CustomStr:143 def __init__(self(empty), sapple):144 self.s→ apple = sappleAll 6 passes — pass 1 is the card above pass sself.s1 apple apple 2 pie pie 3 banana banana 4 kiwi kiwi 5 a a 6 at at words ← [apple]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [apple], CustomStr(wordapple))def __lt__(self, other):
pass 1 of 10146def __lt__(selfpie, otherapple):147 if len(self.s) != len(other.s):148 return len(self.s) < len(other.s)All 10 passes — pass 1 is the card above pass selfother1 pie apple 2 banana apple 3 kiwi apple 4 kiwi pie 5 a apple 6 a kiwi 7 a pie 8 at kiwi 9 at pie 10 at a if len(self.s) != len(other.s):
pass 1 of 10146def __lt__(self, other):147 if len(self.spie) != len(other.sapple):148 return len(self.spie) < len(other.sapple)149 return self.s < other.sAll 10 passes — pass 1 is the card above pass self.sother.s1 pie apple 2 banana apple 3 kiwi apple 4 kiwi pie 5 a apple 6 a kiwi 7 a pie 8 at kiwi 9 at pie 10 at a words ← [pie, apple]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [pie, apple], CustomStr(wordpie))words ← [pie, apple, banana]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [pie, apple, banana], CustomStr(wordbanana))words ← [pie, kiwi, apple, banana]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [pie, kiwi, apple, banana], CustomStr(wordkiwi))words ← [a, pie, kiwi, apple, banana]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [a, pie, kiwi, apple, banana], CustomStr(worda))words ← [a, at, pie, kiwi, apple, banana]
155for word in ["apple", "pie", "banana", "kiwi", "a", "at"]:156 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(words→ [a, at, pie, kiwi, apple, banana], CustomStr(wordat))sorted_insort ← [], data ← [80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
158print("Words sorted by length, then alpha:")159print([str(w) for w in words[a, at, pie, kiwi, apple, banana]])160161# Performance guidance162print("\nPerformance guidance:")163164# insort approach165sorted_insort→ [] = []166data→ [80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] = list(range(80, 0, -1))167for num in data:outputWords sorted by length, then alpha: ['a', 'at', 'pie', 'kiwi', 'apple', 'banana'] Performance guidance:sorted_insort ← [80]
pass 1 of 80166data = list(range(80, 0, -1))167for num80 in data[80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]:168 bisect<module 'bisect' from '/usr/local/lib/python3.12/bisect.py'>.insort(sorted_insort→ [80], num80)80 passes — pass 1 is the card above pass numsorted_insort1 80 [] → [80] 2 79 [80] → [79, 80] 3 78 [79, 80] → [78, 79, 80] 4 77 [78, 79, 80] → [77, 78, 79, 80] 5 76 [77, 78, 79, 80] → [76, 77, 78, 79, 80] 6 75 [76, 77, 78, 79, 80] → [75, 76, 77, 78, 79, 80] 7 74 [75, 76, 77, 78, 79, 80] → [74, 75, 76, 77, 78, 79, 80] 8 73 [74, 75, 76, 77, 78, 79, 80] → [73, 74, 75, 76, 77, 78, 79, 80] 9 72 [73, 74, 75, 76, 77, 78, 79, 80] → [72, 73, 74, 75, 76, 77, 78, 79, 80] ⋯ 69 more passes ⋯ 79 2 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] → [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] 80 1 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] sorted_sort ← [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]
170# sort approach171sorted_sort→ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] = sorted(data[80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])172173print(f"Both approaches agree: {sorted_insort[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] == sorted_sort[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]}")174print("Note: sorted() is faster for bulk operations")175print(" insort is better for incremental additions")outputBoth approaches agree: True Note: sorted() is faster for bulk operations insort is better for incremental additions
insort
Combines bisect and insert into one operation - finds the correct position and inserts the element in O(n) time due to list shifting.
Heap Push and Pop
Basic heap operations:
heappush_pop.py
Replay: real traced execution (multi-file project)
"""heapq basics - heappush and heappop"""
import heapq
# Basic heap operations
print("Basic heap operations:")
heap = []
print(f"Empty heap: {heap}")
# Push elements
heapq.heappush(heap, 5)
print(f"After push(5): {heap}")
heapq.heappush(heap, 3)
print(f"After push(3): {heap}")
heapq.heappush(heap, 7)
print(f"After push(7): {heap}")
heapq.heappush(heap, 1)
print(f"After push(1): {heap}")
# Pop smallest
smallest = heapq.heappop(heap)
print(f"Pop smallest: {smallest}, heap: {heap}")
# Build heap from list
print("\nBuild heap from list:")
numbers = [5, 2, 8, 1, 9, 3, 7]
print(f"Original list: {numbers}")
# Convert to heap in-place
heapq.heapify(numbers)
print(f"After heapify: {numbers}")
print("Note: Not fully sorted, but smallest is at index 0")
# Extract all (in sorted order)
sorted_nums = []
while numbers:
sorted_nums.append(heapq.heappop(numbers))
print(f"Extracted in order: {sorted_nums}")
# Min heap property
print("\nMin heap property:")
heap = []
values = [10, 5, 15, 3, 7, 12, 20]
for val in values:
heapq.heappush(heap, val)
print(f"Heap: {heap}")
print(f"Smallest (heap[0]): {heap[0]}")
print("Popping all:")
while heap:
print(f" Pop: {heapq.heappop(heap)}")
# Priority queue
print("\nPriority queue:")
# Tuples: (priority, item)
tasks = []
heapq.heappush(tasks, (2, "Write code"))
heapq.heappush(tasks, (1, "Fix bug"))
heapq.heappush(tasks, (3, "Review PR"))
heapq.heappush(tasks, (1, "Deploy"))
print("Task queue (by priority):")
while tasks:
priority, task = heapq.heappop(tasks)
print(f" Priority {priority}: {task}")
# Max heap simulation
print("\nMax heap simulation:")
# Negate values for max heap
max_heap = []
values = [5, 2, 8, 1, 9]
for val in values:
heapq.heappush(max_heap, -val)
print(f"Max heap (negated): {max_heap}")
print("Popping largest:")
while max_heap:
largest = -heapq.heappop(max_heap)
print(f" Pop: {largest}")
# heappushpop and heapreplace
print("\nheappushpop and heapreplace:")
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# Push then pop (atomic operation)
result = heapq.heappushpop(heap, 4)
print(f"heappushpop(4): returned {result}, heap: {heap}")
# Pop then push (atomic operation)
result = heapq.heapreplace(heap, 6)
print(f"heapreplace(6): returned {result}, heap: {heap}")
# Task scheduling
print("\nTask scheduling:")
class Task:
def __init__(self, priority, time, name):
self.priority = priority
self.time = time
self.name = name
def __lt__(self, other):
# Sort by priority, then time
if self.priority != other.priority:
return self.priority < other.priority
return self.time < other.time
def __repr__(self):
return f"Task({self.priority}, {self.time}, '{self.name}')"
schedule = []
heapq.heappush(schedule, Task(2, 10, "Backup"))
heapq.heappush(schedule, Task(1, 5, "Deploy"))
heapq.heappush(schedule, Task(1, 8, "Test"))
heapq.heappush(schedule, Task(3, 15, "Report"))
print("Task schedule:")
while schedule:
task = heapq.heappop(schedule)
print(f" {task}")
# Event processing
print("\nEvent processing:")
events = []
# (timestamp, event_type, data)
heapq.heappush(events, (10, "login", "user1"))
heapq.heappush(events, (5, "signup", "user2"))
heapq.heappush(events, (15, "logout", "user1"))
heapq.heappush(events, (8, "login", "user3"))
print("Processing events chronologically:")
while events:
time, event, user = heapq.heappop(events)
print(f" t={time}: {user} {event}")
# Merge sorted sequences
print("\nMerge sorted sequences:")
# Multiple sorted lists
lists = [
[1, 4, 7, 10],
[2, 5, 8, 11],
[3, 6, 9, 12]
]
# Use heap to merge
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
merged = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
merged.append(val)
# Add next element from same list
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
print(f"Lists: {lists}")
print(f"Merged: {merged}")
heap ← [], smallest ← 1, numbers ← [5, 2, 8, 1, 9, 3, 7], sorted_nums ← []
1"""heapq basics - heappush and heappop"""23import heapq45# Basic heap operations6print("Basic heap operations:")78heap→ [] = []9print(f"Empty heap: {heap[]}")1011# Push elements12heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [5], 5)13print(f"After push(5): {heap[5]}")1415heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [3, 5], 3)16print(f"After push(3): {heap[3, 5]}")1718heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [3, 5, 7], 7)19print(f"After push(7): {heap[3, 5, 7]}")2021heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [1, 3, 7, 5], 1)22print(f"After push(1): {heap[1, 3, 7, 5]}")2324# Pop smallest25smallest→ 1 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(heap→ [3, 5, 7])26print(f"Pop smallest: {smallest1}, heap: {heap[3, 5, 7]}")2728# Build heap from list29print("\nBuild heap from list:")3031numbers→ [5, 2, 8, 1, 9, 3, 7] = [5, 2, 8, 1, 9, 3, 7]32print(f"Original list: {numbers[5, 2, 8, 1, 9, 3, 7]}")3334# Convert to heap in-place35heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heapify(numbers→ [1, 2, 3, 5, 9, 8, 7])36print(f"After heapify: {numbers[1, 2, 3, 5, 9, 8, 7]}")37print("Note: Not fully sorted, but smallest is at index 0")3839# Extract all (in sorted order)40sorted_nums→ [] = []41while numbers:outputBasic heap operations: Empty heap: [] After push(5): [5] After push(3): [3, 5] After push(7): [3, 5, 7] After push(1): [1, 3, 7, 5] Pop smallest: 1, heap: [3, 5, 7] Build heap from list: Original list: [5, 2, 8, 1, 9, 3, 7] After heapify: [1, 2, 3, 5, 9, 8, 7] Note: Not fully sorted, but smallest is at index 0sorted_nums ← [1], numbers ← [2, 5, 3, 7, 9, 8]
pass 1 of 740sorted_nums = []41while numbers[1, 2, 3, 5, 9, 8, 7]:42 sorted_nums→ [1].append(heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(numbers→ [2, 5, 3, 7, 9, 8]))All 7 passes — pass 1 is the card above pass sorted_numsnumbers1 [] → [1] [1, 2, 3, 5, 9, 8, 7] → [2, 5, 3, 7, 9, 8] 2 [1] → [1, 2] [2, 5, 3, 7, 9, 8] → [3, 5, 8, 7, 9] 3 [1, 2] → [1, 2, 3] [3, 5, 8, 7, 9] → [5, 7, 8, 9] 4 [1, 2, 3] → [1, 2, 3, 5] [5, 7, 8, 9] → [7, 9, 8] 5 [1, 2, 3, 5] → [1, 2, 3, 5, 7] [7, 9, 8] → [8, 9] 6 [1, 2, 3, 5, 7] → [1, 2, 3, 5, 7, 8] [8, 9] → [9] 7 [1, 2, 3, 5, 7, 8] → [1, 2, 3, 5, 7, 8, 9] [9] → [] heap ← [], values ← [10, 5, 15, 3, 7, 12, 20]
44print(f"Extracted in order: {sorted_nums[1, 2, 3, 5, 7, 8, 9]}")4546# Min heap property47print("\nMin heap property:")4849heap→ [] = []50values→ [10, 5, 15, 3, 7, 12, 20] = [10, 5, 15, 3, 7, 12, 20]outputExtracted in order: [1, 2, 3, 5, 7, 8, 9] Min heap property:heap ← [10]
pass 1 of 752for val10 in values[10, 5, 15, 3, 7, 12, 20]:53 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [10], val10)All 7 passes — pass 1 is the card above pass valheap1 10 [] → [10] 2 5 [10] → [5, 10] 3 15 [5, 10] → [5, 10, 15] 4 3 [5, 10, 15] → [3, 5, 15, 10] 5 7 [3, 5, 15, 10] → [3, 5, 15, 10, 7] 6 12 [3, 5, 15, 10, 7] → [3, 5, 12, 10, 7, 15] 7 20 [3, 5, 12, 10, 7, 15] → [3, 5, 12, 10, 7, 15, 20] print(f"Heap: {heap}")
55print(f"Heap: {heap[3, 5, 12, 10, 7, 15, 20]}")56print(f"Smallest (heap[0]): {heap[0]3}")57print("Popping all:")58while heap:outputHeap: [3, 5, 12, 10, 7, 15, 20] Smallest (heap[0]): 3 Popping all:heap ← [5, 7, 12, 10, 20, 15]
pass 1 of 757print("Popping all:")58while heap[3, 5, 12, 10, 7, 15, 20]:59 print(f" Pop: {heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(heap→ [5, 7, 12, 10, 20, 15])}")output Pop: 3All 7 passes — pass 1 is the card above pass heap1 [3, 5, 12, 10, 7, 15, 20] → [5, 7, 12, 10, 20, 15] 2 [5, 7, 12, 10, 20, 15] → [7, 10, 12, 15, 20] 3 [7, 10, 12, 15, 20] → [10, 15, 12, 20] 4 [10, 15, 12, 20] → [12, 15, 20] 5 [12, 15, 20] → [15, 20] 6 [15, 20] → [20] 7 [20] → [] tasks ← []
61# Priority queue62print("\nPriority queue:")6364# Tuples: (priority, item)65tasks→ [] = []6667heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(tasks→ [(2, 'Write code')], (2, "Write code"))68heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(tasks→ [(1, 'Fix bug'), (2, 'Write code')], (1, "Fix bug"))69heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(tasks→ [(1, 'Fix bug'), (2, 'Write code'), (3, 'Review PR')], (3, "Review PR"))70heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(tasks→ [(1, 'Deploy'), (1, 'Fix bug'), (3, 'Review PR'), (2, 'Write code')], (1, "Deploy"))7172print("Task queue (by priority):")73while tasks:output Priority queue: Task queue (by priority):tasks ← [(1, 'Fix bug'), (2, 'Write code'), (3, 'Review PR')]
pass 1 of 472print("Task queue (by priority):")73while tasks[(1, 'Deploy'), (1, 'Fix bug'), (3, 'Review PR'), (2, 'Write code')]:74 priority→ 1, task→ Deploy = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(tasks→ [(1, 'Fix bug'), (2, 'Write code'), (3, 'Review PR')])75 print(f" Priority {priority1}: {taskDeploy}")output Priority 1: DeployAll 4 passes — pass 1 is the card above pass tasksprioritytask1 [(1, 'Deploy'), (1, 'Fix bug'), (3, 'Review PR'), (2, 'Write code')] → [(1, 'Fix bug'), (2, 'Write code'), (3, 'Review PR')] 1 Deploy 2 [(1, 'Fix bug'), (2, 'Write code'), (3, 'Review PR')] → [(2, 'Write code'), (3, 'Review PR')] 1 Fix bug 3 [(2, 'Write code'), (3, 'Review PR')] → [(3, 'Review PR')] 2 Write code 4 [(3, 'Review PR')] → [] 3 Review PR max_heap ← [], values ← [5, 2, 8, 1, 9]
77# Max heap simulation78print("\nMax heap simulation:")7980# Negate values for max heap81max_heap→ [] = []82values→ [5, 2, 8, 1, 9] = [5, 2, 8, 1, 9]output Max heap simulation:max_heap ← [-5]
pass 1 of 584for val5 in values[5, 2, 8, 1, 9]:85 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(max_heap→ [-5], -val5)All 5 passes — pass 1 is the card above pass valmax_heap1 5 [] → [-5] 2 2 [-5] → [-5, -2] 3 8 [-5, -2] → [-8, -2, -5] 4 1 [-8, -2, -5] → [-8, -2, -5, -1] 5 9 [-8, -2, -5, -1] → [-9, -8, -5, -1, -2] print(f"Max heap (negated): {max_heap}")
87print(f"Max heap (negated): {max_heap[-9, -8, -5, -1, -2]}")88print("Popping largest:")89while max_heap:outputMax heap (negated): [-9, -8, -5, -1, -2] Popping largest:max_heap ← [-8, -2, -5, -1], largest ← 9
pass 1 of 588print("Popping largest:")89while max_heap[-9, -8, -5, -1, -2]:90 largest→ 9 = -heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(max_heap→ [-8, -2, -5, -1])91 print(f" Pop: {largest9}")output Pop: 9All 5 passes — pass 1 is the card above pass max_heaplargest1 [-9, -8, -5, -1, -2] → [-8, -2, -5, -1] 9 2 [-8, -2, -5, -1] → [-5, -2, -1] 8 3 [-5, -2, -1] → [-2, -1] 5 4 [-2, -1] → [-1] 2 5 [-1] → [] 1 heap ← [1, 3, 5, 7, 9], result ← 1, schedule ← []
93# heappushpop and heapreplace94print("\nheappushpop and heapreplace:")9596heap→ [1, 3, 5, 7, 9] = [1, 3, 5, 7, 9]97heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heapify(heap[1, 3, 5, 7, 9])9899# Push then pop (atomic operation)100result→ 1 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappushpop(heap→ [3, 4, 5, 7, 9], 4)101print(f"heappushpop(4): returned {result1}, heap: {heap[3, 4, 5, 7, 9]}")102103# Pop then push (atomic operation)104result→ 3 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heapreplace(heap→ [4, 6, 5, 7, 9], 6)105print(f"heapreplace(6): returned {result3}, heap: {heap[4, 6, 5, 7, 9]}")106107# Task scheduling108print("\nTask scheduling:")109110class Task:111 def __init__(self, priority, time, name):112 self.priority = priority113 self.time = time114 self.name = name115 116 def __lt__(self, other):117 # Sort by priority, then time118 if self.priority != other.priority:119 return self.priority < other.priority120 return self.time < other.time121 122 def __repr__(self):123 return f"Task({self.priority}, {self.time}, '{self.name}')"124125schedule→ [] = []126127heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule[], Task(2, 10, "Backup"))128heapq.heappush(schedule, Task(1, 5, "Deploy"))output heappushpop and heapreplace: heappushpop(4): returned 1, heap: [3, 4, 5, 7, 9] heapreplace(6): returned 3, heap: [4, 6, 5, 7, 9] Task scheduling:self.priority ← 2, self.time ← 10, self.name ← Backup
pass 1 of 4110class Task:111 def __init__(self(empty), priority2, time10, nameBackup):112 self.priority→ 2 = priority2113 self.time→ 10 = time10114 self.name→ Backup = nameBackupAll 4 passes — pass 1 is the card above pass prioritytimenameself.priorityself.timeself.name1 2 10 Backup 2 10 Backup 2 1 5 Deploy 1 5 Deploy 3 1 8 Test 1 8 Test 4 3 15 Report 3 15 Report schedule ← [Task(2, 10, 'Backup')]
127heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule→ [Task(2, 10, 'Backup')], Task(2, 10, "Backup"))128heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule[Task(2, 10, 'Backup')], Task(1, 5, "Deploy"))129heapq.heappush(schedule, Task(1, 8, "Test"))def __lt__(self, other): # Sort by priority, then time
pass 1 of 6116def __lt__(selfTask(1, 5, 'Deploy'), otherTask(2, 10, 'Backup')):117 # Sort by priority, then time118 if self.priority != other.priority:119 return self.priority < other.priorityAll 6 passes — pass 1 is the card above pass selfotherself.timeother.time1 Task(1, 5, 'Deploy') Task(2, 10, 'Backup') — — 2 Task(1, 8, 'Test') Task(1, 5, 'Deploy') 8 5 3 Task(3, 15, 'Report') Task(2, 10, 'Backup') — — 4 Task(2, 10, 'Backup') Task(1, 8, 'Test') — — 5 Task(3, 15, 'Report') Task(1, 8, 'Test') — — 6 Task(3, 15, 'Report') Task(2, 10, 'Backup') — — if self.priority != other.priority:
pass 1 of 5117# Sort by priority, then time118if self.priority1 != other.priority2:119 return self.priority1 < other.priority2120return self.time < other.timeAll 5 passes — pass 1 is the card above pass self.priorityother.priority1 1 2 2 3 2 3 2 1 4 3 1 5 3 2 schedule ← [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup')]
127heapq.heappush(schedule, Task(2, 10, "Backup"))128heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule→ [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup')], Task(1, 5, "Deploy"))129heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule[Task(1, 5, 'Deploy'), Task(2, 10, 'Backup')], Task(1, 8, "Test"))130heapq.heappush(schedule, Task(3, 15, "Report"))schedule ← [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test')]
128heapq.heappush(schedule, Task(1, 5, "Deploy"))129heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule→ [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test')], Task(1, 8, "Test"))130heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule[Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test')], Task(3, 15, "Report"))schedule ← [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test'), Task(3, 15, 'Report')]
129heapq.heappush(schedule, Task(1, 8, "Test"))130heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(schedule→ [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test'), Task(3, 15, 'Report')], Task(3, 15, "Report"))131132print("Task schedule:")133while schedule:outputTask schedule:while schedule:
pass 1 of 4132print("Task schedule:")133while schedule[Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test'), Task(3, 15, 'Report')]:134 task = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(schedule[Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test'), Task(3, 15, 'Report')])135 print(f" {task}")All 4 passes — pass 1 is the card above pass scheduletask1 [Task(1, 5, 'Deploy'), Task(2, 10, 'Backup'), Task(1, 8, 'Test'), Task(3, 15, 'Report')] — 2 [Task(1, 8, 'Test'), Task(2, 10, 'Backup'), Task(3, 15, 'Report')] — 3 [Task(2, 10, 'Backup'), Task(3, 15, 'Report')] → [Task(3, 15, 'Report')] Task(2, 10, 'Backup') 4 [Task(3, 15, 'Report')] → [] Task(3, 15, 'Report') schedule ← [Task(1, 8, 'Test'), Task(2, 10, 'Backup'), Task(3, 15, 'Report')]
133while schedule:134 task→ Task(1, 5, 'Deploy') = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(schedule→ [Task(1, 8, 'Test'), Task(2, 10, 'Backup'), Task(3, 15, 'Report')])135 print(f" {taskTask(1, 5, 'Deploy')}")output Task(1, 5, 'Deploy')schedule ← [Task(2, 10, 'Backup'), Task(3, 15, 'Report')], task ← Task(1, 8, 'Test')
133while schedule:134 task→ Task(1, 8, 'Test') = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(schedule→ [Task(2, 10, 'Backup'), Task(3, 15, 'Report')])135 print(f" {taskTask(1, 8, 'Test')}")output Task(1, 8, 'Test')events ← []
137# Event processing138print("\nEvent processing:")139140events→ [] = []141142# (timestamp, event_type, data)143heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(events→ [(10, 'login', 'user1')], (10, "login", "user1"))144heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(events→ [(5, 'signup', 'user2'), (10, 'login', 'user1')], (5, "signup", "user2"))145heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(events→ [(5, 'signup', 'user2'), (10, 'login', 'user1'), (15, 'logout', 'user1')], (15, "logout", "user1"))146heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(events→ [(5, 'signup', 'user2'), (8, 'login', 'user3'), (15, 'logout', 'user1'), (10, 'login', 'user1')], (8, "login", "user3"))147148print("Processing events chronologically:")149while events:output Event processing: Processing events chronologically:events ← [(8, 'login', 'user3'), (10, 'login', 'user1'), (15, 'logout', 'user1')]
pass 1 of 4148print("Processing events chronologically:")149while events[(5, 'signup', 'user2'), (8, 'login', 'user3'), (15, 'logout', 'user1'), (10, 'login', 'user1')]:150 time→ 5, event→ signup, user→ user2 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(events→ [(8, 'login', 'user3'), (10, 'login', 'user1'), (15, 'logout', 'user1')])151 print(f" t={time5}: {useruser2} {eventsignup}")output t=5: user2 signupAll 4 passes — pass 1 is the card above pass eventstimeeventuser1 [(5, 'signup', 'user2'), (8, 'login', 'user3'), (15, 'logout', 'user1'), (10, 'login', 'user1')] → [(8, 'login', 'user3'), (10, 'login', 'user1'), (15, 'logout', 'user1')] 5 signup user2 2 [(8, 'login', 'user3'), (10, 'login', 'user1'), (15, 'logout', 'user1')] → [(10, 'login', 'user1'), (15, 'logout', 'user1')] 8 login user3 3 [(10, 'login', 'user1'), (15, 'logout', 'user1')] → [(15, 'logout', 'user1')] 10 login user1 4 [(15, 'logout', 'user1')] → [] 15 logout user1 lists ← [[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]], heap ← []
153# Merge sorted sequences154print("\nMerge sorted sequences:")155156# Multiple sorted lists157lists→ [[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]] = [158 [1, 4, 7, 10],159 [2, 5, 8, 11],160 [3, 6, 9, 12]161]162163# Use heap to merge164heap→ [] = []165for i, lst in enumerate(lists):output Merge sorted sequences:for i, lst in enumerate(lists):
pass 1 of 3164heap = []165for i0, lst[1, 4, 7, 10] in enumerate(lists[[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]]):166 if lst:167 heapq.heappush(heap, (lst[0], i, 0))All 3 passes — pass 1 is the card above pass ilst1 0 [1, 4, 7, 10] 2 1 [2, 5, 8, 11] 3 2 [3, 6, 9, 12] heap ← [(1, 0, 0)]
pass 1 of 3165for i, lst in enumerate(lists):166 if lst[1, 4, 7, 10]:167 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [(1, 0, 0)], (lst[0]1, i0, 0))All 3 passes — pass 1 is the card above pass lstlst[0]iheap1 [1, 4, 7, 10] 1 0 [] → [(1, 0, 0)] 2 [2, 5, 8, 11] 2 1 [(1, 0, 0)] → [(1, 0, 0), (2, 1, 0)] 3 [3, 6, 9, 12] 3 2 [(1, 0, 0), (2, 1, 0)] → [(1, 0, 0), (2, 1, 0), (3, 2, 0)] merged ← []
169merged→ [] = []170while heap:heap ← [(2, 1, 0), (3, 2, 0)], val ← 1, list_idx ← 0, elem_idx ← 0
pass 1 of 12169merged = []170while heap[(1, 0, 0), (2, 1, 0), (3, 2, 0)]:171 val→ 1, list_idx→ 0, elem_idx→ 0 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(heap→ [(2, 1, 0), (3, 2, 0)])172 merged→ [1].append(val1)All 12 passes — pass 1 is the card above pass heapvallist_idxelem_idxmerged1 [(1, 0, 0), (2, 1, 0), (3, 2, 0)] → [(2, 1, 0), (3, 2, 0)] 1 0 0 [] → [1] 2 [(2, 1, 0), (3, 2, 0), (4, 0, 1)] → [(3, 2, 0), (4, 0, 1)] 2 1 0 [1] → [1, 2] 3 [(3, 2, 0), (4, 0, 1), (5, 1, 1)] → [(4, 0, 1), (5, 1, 1)] 3 2 0 [1, 2] → [1, 2, 3] 4 [(4, 0, 1), (5, 1, 1), (6, 2, 1)] → [(5, 1, 1), (6, 2, 1)] 4 0 1 [1, 2, 3] → [1, 2, 3, 4] 5 [(5, 1, 1), (6, 2, 1), (7, 0, 2)] → [(6, 2, 1), (7, 0, 2)] 5 1 1 [1, 2, 3, 4] → [1, 2, 3, 4, 5] 6 [(6, 2, 1), (7, 0, 2), (8, 1, 2)] → [(7, 0, 2), (8, 1, 2)] 6 2 1 [1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6] 7 [(7, 0, 2), (8, 1, 2), (9, 2, 2)] → [(8, 1, 2), (9, 2, 2)] 7 0 2 [1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7] 8 [(8, 1, 2), (9, 2, 2), (10, 0, 3)] → [(9, 2, 2), (10, 0, 3)] 8 1 2 [1, 2, 3, 4, 5, 6, 7] → [1, 2, 3, 4, 5, 6, 7, 8] 9 [(9, 2, 2), (10, 0, 3), (11, 1, 3)] → [(10, 0, 3), (11, 1, 3)] 9 2 2 [1, 2, 3, 4, 5, 6, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8, 9] 10 [(10, 0, 3), (11, 1, 3), (12, 2, 3)] → [(11, 1, 3), (12, 2, 3)] 10 0 3 [1, 2, 3, 4, 5, 6, 7, 8, 9] → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 11 [(11, 1, 3), (12, 2, 3)] → [(12, 2, 3)] 11 1 3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 12 [(12, 2, 3)] → [] 12 2 3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] next_val ← 4, heap ← [(2, 1, 0), (3, 2, 0), (4, 0, 1)]
pass 1 of 9174# Add next element from same list175if elem_idx0 + 1 < len(lists[list_idx][1, 4, 7, 10]):176 next_val→ 4 = lists[list_idx][elem_idx + 1]4177 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(heap→ [(2, 1, 0), (3, 2, 0), (4, 0, 1)], (next_val4, list_idx0, elem_idx0 + 1))All 9 passes — pass 1 is the card above pass elem_idxlists[list_idx]lists[list_idx][elem_idx + 1]list_idxnext_valheap1 0 [1, 4, 7, 10] 4 0 4 [(2, 1, 0), (3, 2, 0)] → [(2, 1, 0), (3, 2, 0), (4, 0, 1)] 2 0 [2, 5, 8, 11] 5 1 5 [(3, 2, 0), (4, 0, 1)] → [(3, 2, 0), (4, 0, 1), (5, 1, 1)] 3 0 [3, 6, 9, 12] 6 2 6 [(4, 0, 1), (5, 1, 1)] → [(4, 0, 1), (5, 1, 1), (6, 2, 1)] 4 1 [1, 4, 7, 10] 7 0 7 [(5, 1, 1), (6, 2, 1)] → [(5, 1, 1), (6, 2, 1), (7, 0, 2)] 5 1 [2, 5, 8, 11] 8 1 8 [(6, 2, 1), (7, 0, 2)] → [(6, 2, 1), (7, 0, 2), (8, 1, 2)] 6 1 [3, 6, 9, 12] 9 2 9 [(7, 0, 2), (8, 1, 2)] → [(7, 0, 2), (8, 1, 2), (9, 2, 2)] 7 2 [1, 4, 7, 10] 10 0 10 [(8, 1, 2), (9, 2, 2)] → [(8, 1, 2), (9, 2, 2), (10, 0, 3)] 8 2 [2, 5, 8, 11] 11 1 11 [(9, 2, 2), (10, 0, 3)] → [(9, 2, 2), (10, 0, 3), (11, 1, 3)] 9 2 [3, 6, 9, 12] 12 2 12 [(10, 0, 3), (11, 1, 3)] → [(10, 0, 3), (11, 1, 3), (12, 2, 3)] print(f"Lists: {lists}")
179print(f"Lists: {lists[[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]]}")180print(f"Merged: {merged[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]}")outputLists: [[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]] Merged: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
heap
A binary tree stored in a list where each parent is smaller than its children - enables O(log n) insertion and O(1) access to the minimum element.
Finding Largest and Smallest
Efficient extreme value extraction:
nlargest_nsmallest.py
Replay: real traced execution (multi-file project)
"""heapq.nlargest and nsmallest"""
import heapq
# Basic nsmallest
print("Basic nsmallest:")
numbers = [5, 2, 8, 1, 9, 3, 7, 4, 6]
smallest_3 = heapq.nsmallest(3, numbers)
print(f"Numbers: {numbers}")
print(f"3 smallest: {smallest_3}")
smallest_5 = heapq.nsmallest(5, numbers)
print(f"5 smallest: {smallest_5}")
# Basic nlargest
print("\nBasic nlargest:")
largest_3 = heapq.nlargest(3, numbers)
print(f"3 largest: {largest_3}")
largest_5 = heapq.nlargest(5, numbers)
print(f"5 largest: {largest_5}")
# With key function
print("\nWith key function:")
words = ["apple", "pie", "banana", "kiwi", "strawberry", "fig"]
# Shortest 3 words
shortest = heapq.nsmallest(3, words, key=len)
print(f"Words: {words}")
print(f"3 shortest: {shortest}")
# Longest 3 words
longest = heapq.nlargest(3, words, key=len)
print(f"3 longest: {longest}")
# Custom objects
print("\nCustom objects:")
class Student:
def __init__(self, name, score):
self.name = name
self.score = score
def __repr__(self):
return f"{self.name}({self.score})"
students = [
Student("Alice", 92),
Student("Bob", 85),
Student("Charlie", 78),
Student("David", 95),
Student("Eve", 88)
]
# Top 3 students
top_3 = heapq.nlargest(3, students, key=lambda s: s.score)
print("Top 3 students:")
for s in top_3:
print(f" {s}")
# Bottom 3 students
bottom_3 = heapq.nsmallest(3, students, key=lambda s: s.score)
print("\nBottom 3 students:")
for s in bottom_3:
print(f" {s}")
# Multiple criteria
print("\nMultiple criteria:")
class Product:
def __init__(self, name, price, rating):
self.name = name
self.price = price
self.rating = rating
def __repr__(self):
return f"{self.name}(${ self.price:.2f}, {self.rating}★)"
products = [
Product("Widget", 29.99, 4.5),
Product("Gadget", 49.99, 4.8),
Product("Tool", 19.99, 4.2),
Product("Device", 39.99, 4.7),
Product("Item", 24.99, 4.6)
]
# Cheapest 3
cheapest = heapq.nsmallest(3, products, key=lambda p: p.price)
print("3 cheapest:")
for p in cheapest:
print(f" {p}")
# Highest rated 3
best_rated = heapq.nlargest(3, products, key=lambda p: p.rating)
print("\n3 highest rated:")
for p in best_rated:
print(f" {p}")
# Performance comparison
print("\nPerformance comparison:")
import random
random.seed(42)
data = [random.randint(1, 1000) for _ in range(40)]
# heapq.nsmallest
smallest_10 = heapq.nsmallest(10, data)
print(f"10 smallest (heapq): {smallest_10}")
# Alternative: sort and slice
sorted_smallest = sorted(data)[:10]
print(f"10 smallest (sorted): {sorted_smallest}")
print("\nNote: heapq is faster when n is much smaller than len(data)")
# Top-K frequent
print("\nTop-K frequent:")
from collections import Counter
words = ["apple", "banana", "apple", "cherry", "banana",
"apple", "date", "cherry", "banana", "banana"]
# Count frequencies
counter = Counter(words)
# Top 3 most frequent
top_3_freq = heapq.nlargest(3, counter.items(), key=lambda x: x[1])
print(f"Words: {words}")
print("Top 3 frequent:")
for word, count in top_3_freq:
print(f" {word}: {count}")
# Weighted selection
print("\nWeighted selection:")
tasks = [
{"name": "Fix bug", "priority": 1, "time": 2},
{"name": "Review", "priority": 2, "time": 1},
{"name": "Deploy", "priority": 1, "time": 3},
{"name": "Test", "priority": 3, "time": 2}
]
# Highest priority (lower number = higher priority)
urgent = heapq.nsmallest(2, tasks, key=lambda t: t["priority"])
print("2 most urgent tasks:")
for task in urgent:
print(f" {task}")
# Quickest tasks
quick = heapq.nsmallest(2, tasks, key=lambda t: t["time"])
print("\n2 quickest tasks:")
for task in quick:
print(f" {task}")
# Median calculation
print("\nMedian calculation:")
numbers = [5, 2, 8, 1, 9, 3, 7, 4, 6]
# Find median using heaps
n = len(numbers)
if n % 2 == 1:
median = heapq.nsmallest(n // 2 + 1, numbers)[-1]
else:
middle = heapq.nsmallest(n // 2 + 1, numbers)
median = (middle[-1] + middle[-2]) / 2
print(f"Numbers: {numbers}")
print(f"Median: {median}")
# Leaderboard
print("\nLeaderboard:")
scores = [
("Alice", 850),
("Bob", 920),
("Charlie", 780),
("David", 900),
("Eve", 870),
("Frank", 810)
]
# Top 3 players
top_3_players = heapq.nlargest(3, scores, key=lambda x: x[1])
print("Leaderboard:")
for i, (name, score) in enumerate(top_3_players, 1):
print(f" #{i}: {name} - {score}")
numbers ← [5, 2, 8, 1, 9, 3, 7, 4, 6], smallest_3 ← [1, 2, 3]
1"""heapq.nlargest and nsmallest"""23import heapq45# Basic nsmallest6print("Basic nsmallest:")78numbers→ [5, 2, 8, 1, 9, 3, 7, 4, 6] = [5, 2, 8, 1, 9, 3, 7, 4, 6]910smallest_3→ [1, 2, 3] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(3, numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])11print(f"Numbers: {numbers[5, 2, 8, 1, 9, 3, 7, 4, 6]}")12print(f"3 smallest: {smallest_3[1, 2, 3]}")1314smallest_5→ [1, 2, 3, 4, 5] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(5, numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])15print(f"5 smallest: {smallest_5[1, 2, 3, 4, 5]}")1617# Basic nlargest18print("\nBasic nlargest:")1920largest_3→ [9, 8, 7] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])21print(f"3 largest: {largest_3[9, 8, 7]}")2223largest_5→ [9, 8, 7, 6, 5] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(5, numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])24print(f"5 largest: {largest_5[9, 8, 7, 6, 5]}")2526# With key function27print("\nWith key function:")2829words→ ['apple', 'pie', 'banana', 'kiwi', 'strawberry', 'fig'] = ["apple", "pie", "banana", "kiwi", "strawberry", "fig"]3031# Shortest 3 words32shortest→ ['pie', 'fig', 'kiwi'] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(3, words['apple', 'pie', 'banana', 'kiwi', 'strawberry', 'fig'], key=len)33print(f"Words: {words['apple', 'pie', 'banana', 'kiwi', 'strawberry', 'fig']}")34print(f"3 shortest: {shortest['pie', 'fig', 'kiwi']}")3536# Longest 3 words37longest→ ['strawberry', 'banana', 'apple'] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, words['apple', 'pie', 'banana', 'kiwi', 'strawberry', 'fig'], key=len)38print(f"3 longest: {longest['strawberry', 'banana', 'apple']}")3940# Custom objects41print("\nCustom objects:")4243class Student:44 def __init__(self, name, score):45 self.name = name46 self.score = score47 48 def __repr__(self):49 return f"{self.name}({self.score})"5051students = [52 Student("Alice", 92),53 Student("Bob", 85),54 Student("Charlie", 78),55 Student("David", 95),56 Student("Eve", 88)57]outputBasic nsmallest: Numbers: [5, 2, 8, 1, 9, 3, 7, 4, 6] 3 smallest: [1, 2, 3] 5 smallest: [1, 2, 3, 4, 5] Basic nlargest: 3 largest: [9, 8, 7] 5 largest: [9, 8, 7, 6, 5] With key function: Words: ['apple', 'pie', 'banana', 'kiwi', 'strawberry', 'fig'] 3 shortest: ['pie', 'fig', 'kiwi'] 3 longest: ['strawberry', 'banana', 'apple'] Custom objects:self.name ← Alice, self.score ← 92
pass 1 of 543class Student:44 def __init__(self(empty), nameAlice, score92):45 self.name→ Alice = nameAlice46 self.score→ 92 = score92All 5 passes — pass 1 is the card above pass namescoreself.nameself.score1 Alice 92 Alice 92 2 Bob 85 Bob 85 3 Charlie 78 Charlie 78 4 David 95 David 95 5 Eve 88 Eve 88 students ← [Alice(92), Bob(85), Charlie(78), David(95), Eve(88)]
51students→ [Alice(92), Bob(85), Charlie(78), David(95), Eve(88)] = [52 Student("Alice", 92),53 Student("Bob", 85),54 Student("Charlie", 78),55 Student("David", 95),56 Student("Eve", 88)57]5859# Top 3 students60top_3→ [David(95), Alice(92), Eve(88)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, students[Alice(92), Bob(85), Charlie(78), David(95), Eve(88)], key=lambda s: s.score)61print("Top 3 students:")62for s in top_3:outputTop 3 students:for s in top_3:
pass 1 of 361print("Top 3 students:")62for sDavid(95) in top_3[David(95), Alice(92), Eve(88)]:63 print(f" {sDavid(95)}")output David(95)All 3 passes — pass 1 is the card above pass s1 David(95) 2 Alice(92) 3 Eve(88) bottom_3 ← [Charlie(78), Bob(85), Eve(88)]
65# Bottom 3 students66bottom_3→ [Charlie(78), Bob(85), Eve(88)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(3, students[Alice(92), Bob(85), Charlie(78), David(95), Eve(88)], key=lambda s: s.score)67print("\nBottom 3 students:")68for s in bottom_3:output Bottom 3 students:for s in bottom_3:
pass 1 of 367print("\nBottom 3 students:")68for sCharlie(78) in bottom_3[Charlie(78), Bob(85), Eve(88)]:69 print(f" {sCharlie(78)}")output Charlie(78)All 3 passes — pass 1 is the card above pass s1 Charlie(78) 2 Bob(85) 3 Eve(88) print(" Multiple criteria:")
71# Multiple criteria72print("\nMultiple criteria:")7374class Product:75 def __init__(self, name, price, rating):76 self.name = name77 self.price = price78 self.rating = rating79 80 def __repr__(self):81 return f"{self.name}(${ self.price:.2f}, {self.rating}★)"8283products = [84 Product("Widget", 29.99, 4.5),85 Product("Gadget", 49.99, 4.8),86 Product("Tool", 19.99, 4.2),87 Product("Device", 39.99, 4.7),88 Product("Item", 24.99, 4.6)89]output Multiple criteria:self.name ← Widget, self.price ← 29.99, self.rating ← 4.5
pass 1 of 574class Product:75 def __init__(self(empty), nameWidget, price29.99, rating4.5):76 self.name→ Widget = nameWidget77 self.price→ 29.99 = price29.9978 self.rating→ 4.5 = rating4.5All 5 passes — pass 1 is the card above pass namepriceratingself.nameself.priceself.rating1 Widget 29.99 4.5 Widget 29.99 4.5 2 Gadget 49.99 4.8 Gadget 49.99 4.8 3 Tool 19.99 4.2 Tool 19.99 4.2 4 Device 39.99 4.7 Device 39.99 4.7 5 Item 24.99 4.6 Item 24.99 4.6 products ← [Widget($29.99, 4.5★), Gadget($49.99, 4.8★), Tool($19.99, 4.2★), Device($39.99, 4.7★), Item($24.99, 4.6★)]
83products→ [Widget($29.99, 4.5★), Gadget($49.99, 4.8★), Tool($19.99, 4.2★), Device($39.99, 4.7★), Item($24.99, 4.6★)] = [84 Product("Widget", 29.99, 4.5),85 Product("Gadget", 49.99, 4.8),86 Product("Tool", 19.99, 4.2),87 Product("Device", 39.99, 4.7),88 Product("Item", 24.99, 4.6)89]9091# Cheapest 392cheapest→ [Tool($19.99, 4.2★), Item($24.99, 4.6★), Widget($29.99, 4.5★)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(3, products[Widget($29.99, 4.5★), Gadget($49.99, 4.8★), Tool($19.99, 4.2★), Device($39.99, 4.7★), Item($24.99, 4.6★)], key=lambda p: p.price)93print("3 cheapest:")94for p in cheapest:output3 cheapest:for p in cheapest:
pass 1 of 393print("3 cheapest:")94for pTool($19.99, 4.2★) in cheapest[Tool($19.99, 4.2★), Item($24.99, 4.6★), Widget($29.99, 4.5★)]:95 print(f" {pTool($19.99, 4.2★)}")output Tool($19.99, 4.2★)All 3 passes — pass 1 is the card above pass p1 Tool($19.99, 4.2★) 2 Item($24.99, 4.6★) 3 Widget($29.99, 4.5★) best_rated ← [Gadget($49.99, 4.8★), Device($39.99, 4.7★), Item($24.99, 4.6★)]
97# Highest rated 398best_rated→ [Gadget($49.99, 4.8★), Device($39.99, 4.7★), Item($24.99, 4.6★)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, products[Widget($29.99, 4.5★), Gadget($49.99, 4.8★), Tool($19.99, 4.2★), Device($39.99, 4.7★), Item($24.99, 4.6★)], key=lambda p: p.rating)99print("\n3 highest rated:")100for p in best_rated:output 3 highest rated:for p in best_rated:
pass 1 of 399print("\n3 highest rated:")100for pGadget($49.99, 4.8★) in best_rated[Gadget($49.99, 4.8★), Device($39.99, 4.7★), Item($24.99, 4.6★)]:101 print(f" {pGadget($49.99, 4.8★)}")output Gadget($49.99, 4.8★)All 3 passes — pass 1 is the card above pass p1 Gadget($49.99, 4.8★) 2 Device($39.99, 4.7★) 3 Item($24.99, 4.6★) data ← [655, 115, 26, 760, 282, 251, 229, 143, 755, 105, 693, 759, 914, 559, 90, 605, 433, 33, 31, 96, 224, 239, 518, 617, 28, 575, 204, 734, 666, 719, 559, 430, 226, 460, 604, 285, 829, 891, 7, 778]
103# Performance comparison104print("\nPerformance comparison:")105106import random107random<module 'random' from '/usr/local/lib/python3.12/random.py'>.seed(42)108109data→ [655, 115, 26, 760, 282, 251, 229, 143, 755, 105, 693, 759, 914, 559, 90, 605, 433, 33, 31, 96, 224, 239, 518, 617, 28, 575, 204, 734, 666, 719, 559, 430, 226, 460, 604, 285, 829, 891, 7, 778] = [random<module 'random' from '/usr/local/lib/python3.12/random.py'>.randint(1, 1000) for _ in range(40)]110111# heapq.nsmallest112smallest_10→ [7, 26, 28, 31, 33, 90, 96, 105, 115, 143] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(10, data[655, 115, 26, 760, 282, 251, 229, 143, 755, 105, 693, 759, 914, 559, 90, 605, 433, 33, 31, 96, 224, 239, 518, 617, 28, 575, 204, 734, 666, 719, 559, 430, 226, 460, 604, 285, 829, 891, 7, 778])113print(f"10 smallest (heapq): {smallest_10[7, 26, 28, 31, 33, 90, 96, 105, 115, 143]}")114115# Alternative: sort and slice116sorted_smallest→ [7, 26, 28, 31, 33, 90, 96, 105, 115, 143] = sorted(data[655, 115, 26, 760, 282, 251, 229, 143, 755, 105, 693, 759, 914, 559, 90, 605, 433, 33, 31, 96, 224, 239, 518, 617, 28, 575, 204, 734, 666, 719, 559, 430, 226, 460, 604, 285, 829, 891, 7, 778])[:10]117print(f"10 smallest (sorted): {sorted_smallest[7, 26, 28, 31, 33, 90, 96, 105, 115, 143]}")118119print("\nNote: heapq is faster when n is much smaller than len(data)")120121# Top-K frequent122print("\nTop-K frequent:")123124from collections import Counter125126words→ ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date', 'cherry', 'banana', 'banana'] = ["apple", "banana", "apple", "cherry", "banana", 127 "apple", "date", "cherry", "banana", "banana"]128129# Count frequencies130counter→ Counter({'banana': 4, 'apple': 3, 'cherry': 2, 'date': 1}) = Counter(words['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date', 'cherry', 'banana', 'banana'])131132# Top 3 most frequent133top_3_freq→ [('banana', 4), ('apple', 3), ('cherry', 2)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, counterCounter({'banana': 4, 'apple': 3, 'cherry': 2, 'date': 1}).items(), key=lambda x: x[1])134135print(f"Words: {words['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date', 'cherry', 'banana', 'banana']}")136print("Top 3 frequent:")137for word, count in top_3_freq:output Performance comparison: 10 smallest (heapq): [7, 26, 28, 31, 33, 90, 96, 105, 115, 143] 10 smallest (sorted): [7, 26, 28, 31, 33, 90, 96, 105, 115, 143] Note: heapq is faster when n is much smaller than len(data) Top-K frequent: Words: ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple', 'date', 'cherry', 'banana', 'banana'] Top 3 frequent:for word, count in top_3_freq:
pass 1 of 3136print("Top 3 frequent:")137for wordbanana, count4 in top_3_freq[('banana', 4), ('apple', 3), ('cherry', 2)]:138 print(f" {wordbanana}: {count4}")output banana: 4All 3 passes — pass 1 is the card above pass wordcount1 banana 4 2 apple 3 3 cherry 2 tasks ← [{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Deploy', 'priority': 1, 'time': 3}, {'name': 'Test', 'priority': 3, 'time': 2}]
140# Weighted selection141print("\nWeighted selection:")142143tasks→ [{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Deploy', 'priority': 1, 'time': 3}, {'name': 'Test', 'priority': 3, 'time': 2}] = [144 {"name": "Fix bug", "priority": 1, "time": 2},145 {"name": "Review", "priority": 2, "time": 1},146 {"name": "Deploy", "priority": 1, "time": 3},147 {"name": "Test", "priority": 3, "time": 2}148]149150# Highest priority (lower number = higher priority)151urgent→ [{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Deploy', 'priority': 1, 'time': 3}] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(2, tasks[{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Deploy', 'priority': 1, 'time': 3}, {'name': 'Test', 'priority': 3, 'time': 2}], key=lambda t: t["priority"])152print("2 most urgent tasks:")153for task in urgent:output Weighted selection: 2 most urgent tasks:for task in urgent:
pass 1 of 2152print("2 most urgent tasks:")153for task{'name': 'Fix bug', 'priority': 1, 'time': 2} in urgent[{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Deploy', 'priority': 1, 'time': 3}]:154 print(f" {task{'name': 'Fix bug', 'priority': 1, 'time': 2}}")output {'name': 'Fix bug', 'priority': 1, 'time': 2}for task in urgent:
pass 2 of 2152print("2 most urgent tasks:")153for task{'name': 'Deploy', 'priority': 1, 'time': 3} in urgent[{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Deploy', 'priority': 1, 'time': 3}]:154 print(f" {task{'name': 'Deploy', 'priority': 1, 'time': 3}}")output {'name': 'Deploy', 'priority': 1, 'time': 3}quick ← [{'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Fix bug', 'priority': 1, 'time': 2}]
156# Quickest tasks157quick→ [{'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Fix bug', 'priority': 1, 'time': 2}] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(2, tasks[{'name': 'Fix bug', 'priority': 1, 'time': 2}, {'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Deploy', 'priority': 1, 'time': 3}, {'name': 'Test', 'priority': 3, 'time': 2}], key=lambda t: t["time"])158print("\n2 quickest tasks:")159for task in quick:output 2 quickest tasks:for task in quick:
pass 1 of 2158print("\n2 quickest tasks:")159for task{'name': 'Review', 'priority': 2, 'time': 1} in quick[{'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Fix bug', 'priority': 1, 'time': 2}]:160 print(f" {task{'name': 'Review', 'priority': 2, 'time': 1}}")output {'name': 'Review', 'priority': 2, 'time': 1}for task in quick:
pass 2 of 2158print("\n2 quickest tasks:")159for task{'name': 'Fix bug', 'priority': 1, 'time': 2} in quick[{'name': 'Review', 'priority': 2, 'time': 1}, {'name': 'Fix bug', 'priority': 1, 'time': 2}]:160 print(f" {task{'name': 'Fix bug', 'priority': 1, 'time': 2}}")output {'name': 'Fix bug', 'priority': 1, 'time': 2}numbers ← [5, 2, 8, 1, 9, 3, 7, 4, 6], n ← 9
162# Median calculation163print("\nMedian calculation:")164165numbers→ [5, 2, 8, 1, 9, 3, 7, 4, 6] = [5, 2, 8, 1, 9, 3, 7, 4, 6]166167# Find median using heaps168n→ 9 = len(numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])169if n % 2 == 1:output Median calculation:median ← 5
168n = len(numbers)169if n9 % 2 == 1:170 median→ 5 = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nsmallest(n9 // 2 + 1, numbers[5, 2, 8, 1, 9, 3, 7, 4, 6])[-1]171else:scores ← [('Alice', 850), ('Bob', 920), ('Charlie', 780), ('David', 900), ('Eve', 870), ('Frank', 810)]
175print(f"Numbers: {numbers[5, 2, 8, 1, 9, 3, 7, 4, 6]}")176print(f"Median: {median5}")177178# Leaderboard179print("\nLeaderboard:")180181scores→ [('Alice', 850), ('Bob', 920), ('Charlie', 780), ('David', 900), ('Eve', 870), ('Frank', 810)] = [182 ("Alice", 850),183 ("Bob", 920),184 ("Charlie", 780),185 ("David", 900),186 ("Eve", 870),187 ("Frank", 810)188]189190# Top 3 players191top_3_players→ [('Bob', 920), ('David', 900), ('Eve', 870)] = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.nlargest(3, scores[('Alice', 850), ('Bob', 920), ('Charlie', 780), ('David', 900), ('Eve', 870), ('Frank', 810)], key=lambda x: x[1])192193print("Leaderboard:")194for i, (name, score) in enumerate(top_3_players, 1):outputNumbers: [5, 2, 8, 1, 9, 3, 7, 4, 6] Median: 5 Leaderboard: Leaderboard:for i, (name, score) in enumerate(top_3_players, 1):
pass 1 of 3193print("Leaderboard:")194for i1, (nameBob, score920) in enumerate(top_3_players[('Bob', 920), ('David', 900), ('Eve', 870)], 1):195 print(f" #{i1}: {nameBob} - {score920}")output #1: Bob - 920All 3 passes — pass 1 is the card above pass inamescore1 1 Bob 920 2 2 David 900 3 3 Eve 870
Priority Queue Pattern
Using heaps for task scheduling:
priority_queue.py
Replay: real traced execution (multi-file project)
"""Heap as priority queue"""
import heapq
from dataclasses import dataclass, field
from typing import Any
# Basic priority queue
print("Basic priority queue:")
pq = []
# Add tasks with priorities
heapq.heappush(pq, (2, "Medium priority task"))
heapq.heappush(pq, (1, "High priority task"))
heapq.heappush(pq, (3, "Low priority task"))
heapq.heappush(pq, (1, "Another high priority"))
print("Processing by priority:")
while pq:
priority, task = heapq.heappop(pq)
print(f" Priority {priority}: {task}")
# Priority queue with timestamp
print("\nPriority queue with timestamp:")
import time
pq = []
# (priority, timestamp, task)
heapq.heappush(pq, (1, 0.003, "Task C"))
heapq.heappush(pq, (1, 0.001, "Task A"))
heapq.heappush(pq, (1, 0.002, "Task B"))
heapq.heappush(pq, (2, 0.004, "Task D"))
print("Same priority sorted by timestamp:")
while pq:
priority, ts, task = heapq.heappop(pq)
print(f" {task} (p={priority}, t={ts})")
# Priority queue class
print("\nPriority queue class:")
@dataclass(order=True)
class PrioritizedItem:
priority: int
item: Any = field(compare=False)
class PriorityQueue:
def __init__(self):
self.heap = []
self.counter = 0
def push(self, item, priority):
# Use counter to break ties (FIFO for same priority)
entry = (priority, self.counter, item)
heapq.heappush(self.heap, entry)
self.counter += 1
def pop(self):
priority, _, item = heapq.heappop(self.heap)
return item, priority
def is_empty(self):
return len(self.heap) == 0
queue = PriorityQueue()
queue.push("Fix bug", 1)
queue.push("Write docs", 3)
queue.push("Deploy", 1)
queue.push("Test", 2)
print("Custom priority queue:")
while not queue.is_empty():
task, priority = queue.pop()
print(f" Priority {priority}: {task}")
# Task scheduler
print("\nTask scheduler:")
class TaskScheduler:
def __init__(self):
self.tasks = []
def add_task(self, name, priority, duration):
heapq.heappush(self.tasks, (priority, duration, name))
def execute_all(self):
total_time = 0
while self.tasks:
priority, duration, name = heapq.heappop(self.tasks)
print(f" Executing: {name} (priority={priority}, duration={duration})")
total_time += duration
return total_time
scheduler = TaskScheduler()
scheduler.add_task("Backup database", 2, 30)
scheduler.add_task("Deploy hotfix", 1, 15)
scheduler.add_task("Update docs", 3, 45)
scheduler.add_task("Security patch", 1, 20)
print("Task execution order:")
total = scheduler.execute_all()
print(f"Total time: {total} minutes")
# Event simulator
print("\nEvent simulator:")
class Event:
def __init__(self, time, event_type, handler):
self.time = time
self.event_type = event_type
self.handler = handler
def __lt__(self, other):
return self.time < other.time
def execute(self):
return self.handler()
class EventSimulator:
def __init__(self):
self.events = []
self.current_time = 0
def schedule(self, delay, event_type, handler):
event = Event(self.current_time + delay, event_type, handler)
heapq.heappush(self.events, event)
def run(self):
while self.events:
event = heapq.heappop(self.events)
self.current_time = event.time
print(f"t={self.current_time}: {event.event_type}")
event.execute()
sim = EventSimulator()
sim.schedule(10, "Login", lambda: None)
sim.schedule(5, "Page load", lambda: None)
sim.schedule(15, "Click button", lambda: None)
sim.schedule(8, "Fetch data", lambda: None)
print("Event simulation:")
sim.run()
# Dijkstra's algorithm
print("\nDijkstra's algorithm:")
def dijkstra(graph, start):
"""Find shortest paths from start to all nodes"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, current_node = heapq.heappop(pq)
# Skip if we found a better path already
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('D', 3)],
'C': [('B', 1), ('D', 5)],
'D': []
}
distances = dijkstra(graph, 'A')
print("Shortest distances from A:")
for node, dist in sorted(distances.items()):
print(f" to {node}: {dist}")
# Job queue
print("\nJob queue:")
class Job:
def __init__(self, job_id, priority, name):
self.id = job_id
self.priority = priority
self.name = name
def __lt__(self, other):
# Lower priority number = higher priority
if self.priority != other.priority:
return self.priority < other.priority
return self.id < other.id
def __repr__(self):
return f"Job({self.id}, p={self.priority}, '{self.name}')"
class JobQueue:
def __init__(self):
self.queue = []
def add_job(self, job):
heapq.heappush(self.queue, job)
def get_next(self):
return heapq.heappop(self.queue) if self.queue else None
def size(self):
return len(self.queue)
jq = JobQueue()
jq.add_job(Job(1, 2, "Process data"))
jq.add_job(Job(2, 1, "Critical update"))
jq.add_job(Job(3, 3, "Send emails"))
jq.add_job(Job(4, 1, "Security scan"))
print(f"Job queue size: {jq.size()}")
print("Processing jobs:")
while job := jq.get_next():
print(f" {job}")
# Bandwidth allocation
print("\nBandwidth allocation:")
class Connection:
def __init__(self, user, priority, bandwidth):
self.user = user
self.priority = priority
self.bandwidth = bandwidth
def __lt__(self, other):
return self.priority < other.priority
connections = []
heapq.heappush(connections, Connection("user1", 2, 100))
heapq.heappush(connections, Connection("user2", 1, 50))
heapq.heappush(connections, Connection("user3", 3, 75))
heapq.heappush(connections, Connection("user4", 1, 25))
total_bandwidth = 200
allocated = 0
print("Allocating bandwidth:")
while connections and allocated < total_bandwidth:
conn = heapq.heappop(connections)
if allocated + conn.bandwidth <= total_bandwidth:
print(f" {conn.user}: {conn.bandwidth} MB/s (priority {conn.priority})")
allocated += conn.bandwidth
else:
remaining = total_bandwidth - allocated
print(f" {conn.user}: {remaining} MB/s (partial, priority {conn.priority})")
allocated = total_bandwidth
pq ← []
1"""Heap as priority queue"""23import heapq4from dataclasses import dataclass, field5from typing import Any67# Basic priority queue8print("Basic priority queue:")910pq→ [] = []1112# Add tasks with priorities13heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(2, 'Medium priority task')], (2, "Medium priority task"))14heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 'High priority task'), (2, 'Medium priority task')], (1, "High priority task"))15heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 'High priority task'), (2, 'Medium priority task'), (3, 'Low priority task')], (3, "Low priority task"))16heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 'Another high priority'), (1, 'High priority task'), (3, 'Low priority task'), (2, 'Medium priority task')], (1, "Another high priority"))1718print("Processing by priority:")19while pq:outputBasic priority queue: Processing by priority:pq ← [(1, 'High priority task'), (2, 'Medium priority task'), (3, 'Low priority task')]
pass 1 of 418print("Processing by priority:")19while pq[(1, 'Another high priority'), (1, 'High priority task'), (3, 'Low priority task'), (2, 'Medium priority task')]:20 priority→ 1, task→ Another high priority = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(pq→ [(1, 'High priority task'), (2, 'Medium priority task'), (3, 'Low priority task')])21 print(f" Priority {priority1}: {taskAnother high priority}")output Priority 1: Another high priorityAll 4 passes — pass 1 is the card above pass pqprioritytask1 [(1, 'Another high priority'), (1, 'High priority task'), (3, 'Low priority task'), (2, 'Medium priority task')] → [(1, 'High priority task'), (2, 'Medium priority task'), (3, 'Low priority task')] 1 Another high priority 2 [(1, 'High priority task'), (2, 'Medium priority task'), (3, 'Low priority task')] → [(2, 'Medium priority task'), (3, 'Low priority task')] 1 High priority task 3 [(2, 'Medium priority task'), (3, 'Low priority task')] → [(3, 'Low priority task')] 2 Medium priority task 4 [(3, 'Low priority task')] → [] 3 Low priority task pq ← []
23# Priority queue with timestamp24print("\nPriority queue with timestamp:")2526import time2728pq→ [] = []2930# (priority, timestamp, task)31heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 0.003, 'Task C')], (1, 0.003, "Task C"))32heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 0.001, 'Task A'), (1, 0.003, 'Task C')], (1, 0.001, "Task A"))33heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 0.001, 'Task A'), (1, 0.003, 'Task C'), (1, 0.002, 'Task B')], (1, 0.002, "Task B"))34heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(1, 0.001, 'Task A'), (1, 0.003, 'Task C'), (1, 0.002, 'Task B'), (2, 0.004, 'Task D')], (2, 0.004, "Task D"))3536print("Same priority sorted by timestamp:")37while pq:output Priority queue with timestamp: Same priority sorted by timestamp:pq ← [(1, 0.002, 'Task B'), (1, 0.003, 'Task C'), (2, 0.004, 'Task D')]
pass 1 of 436print("Same priority sorted by timestamp:")37while pq[(1, 0.001, 'Task A'), (1, 0.003, 'Task C'), (1, 0.002, 'Task B'), (2, 0.004, 'Task D')]:38 priority→ 1, ts→ 0.001, task→ Task A = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(pq→ [(1, 0.002, 'Task B'), (1, 0.003, 'Task C'), (2, 0.004, 'Task D')])39 print(f" {taskTask A} (p={priority1}, t={ts0.001})")output Task A (p=1, t=0.001)All 4 passes — pass 1 is the card above pass pqprioritytstask1 [(1, 0.001, 'Task A'), (1, 0.003, 'Task C'), (1, 0.002, 'Task B'), (2, 0.004, 'Task D')] → [(1, 0.002, 'Task B'), (1, 0.003, 'Task C'), (2, 0.004, 'Task D')] 1 0.001 Task A 2 [(1, 0.002, 'Task B'), (1, 0.003, 'Task C'), (2, 0.004, 'Task D')] → [(1, 0.003, 'Task C'), (2, 0.004, 'Task D')] 1 0.002 Task B 3 [(1, 0.003, 'Task C'), (2, 0.004, 'Task D')] → [(2, 0.004, 'Task D')] 1 0.003 Task C 4 [(2, 0.004, 'Task D')] → [] 2 0.004 Task D item ← (empty)
41# Priority queue class42print("\nPriority queue class:")4344@dataclass(order=True)45class PrioritizedItem:46 priority2: int47 item→ (empty): Any = field(compare=False)4849class PriorityQueue:50 def __init__(self):51 self.heap = []52 self.counter = 053 54 def push(self, item, priority):55 # Use counter to break ties (FIFO for same priority)56 entry = (priority, self.counter, item)57 heapq.heappush(self.heap, entry)58 self.counter += 159 60 def pop(self):61 priority, _, item = heapq.heappop(self.heap)62 return item, priority63 64 def is_empty(self):65 return len(self.heap) == 06667queue = PriorityQueue()68queue.push("Fix bug", 1)output Priority queue class:self.heap ← [], self.counter ← 0
49class PriorityQueue:50 def __init__(self⟨PriorityQueue A⟩):51 self.heap→ [] = []52 self.counter→ 0 = 0queue ← ⟨PriorityQueue A⟩
67queue→ ⟨PriorityQueue A⟩ = PriorityQueue()68queue⟨PriorityQueue A⟩.push("Fix bug", 1)69queue.push("Write docs", 3)entry ← (1, 0, 'Fix bug'), self.heap ← [(1, 0, 'Fix bug')], self.counter ← 1
pass 1 of 454def push(self⟨PriorityQueue A⟩, itemFix bug, priority1):55 # Use counter to break ties (FIFO for same priority)56 entry→ (1, 0, 'Fix bug') = (priority1, self.counter0, itemFix bug)57 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.heap→ [(1, 0, 'Fix bug')], entry(1, 0, 'Fix bug'))58 self.counter→ 1 += 1All 4 passes — pass 1 is the card above pass itempriorityentryself.heapself.counter1 Fix bug 1 (1, 0, 'Fix bug') [] → [(1, 0, 'Fix bug')] 0 → 1 2 Write docs 3 (3, 1, 'Write docs') [(1, 0, 'Fix bug')] → [(1, 0, 'Fix bug'), (3, 1, 'Write docs')] 1 → 2 3 Deploy 1 (1, 2, 'Deploy') [(1, 0, 'Fix bug'), (3, 1, 'Write docs')] → [(1, 0, 'Fix bug'), (3, 1, 'Write docs'), (1, 2, 'Deploy')] 2 → 3 4 Test 2 (2, 3, 'Test') [(1, 0, 'Fix bug'), (3, 1, 'Write docs'), (1, 2, 'Deploy')] → [(1, 0, 'Fix bug'), (2, 3, 'Test'), (1, 2, 'Deploy'), (3, 1, 'Write docs')] 3 → 4 queue.push("Fix bug", 1)
67queue = PriorityQueue()68queue⟨PriorityQueue A⟩.push("Fix bug", 1)69queue⟨PriorityQueue A⟩.push("Write docs", 3)70queue.push("Deploy", 1)queue.push("Write docs", 3)
68queue.push("Fix bug", 1)69queue⟨PriorityQueue A⟩.push("Write docs", 3)70queue⟨PriorityQueue A⟩.push("Deploy", 1)71queue.push("Test", 2)queue.push("Deploy", 1)
69queue.push("Write docs", 3)70queue⟨PriorityQueue A⟩.push("Deploy", 1)71queue⟨PriorityQueue A⟩.push("Test", 2)queue.push("Test", 2)
70queue.push("Deploy", 1)71queue⟨PriorityQueue A⟩.push("Test", 2)7273print("Custom priority queue:")74while not queue.is_empty():outputCustom priority queue:def is_empty(self):
pass 1 of 564def is_empty(self⟨PriorityQueue A⟩):65 return len(self.heap[(1, 0, 'Fix bug'), (2, 3, 'Test'), (1, 2, 'Deploy'), (3, 1, 'Write docs')]) == 0All 5 passes — pass 1 is the card above pass self.heap1 [(1, 0, 'Fix bug'), (2, 3, 'Test'), (1, 2, 'Deploy'), (3, 1, 'Write docs')] 2 [(1, 2, 'Deploy'), (2, 3, 'Test'), (3, 1, 'Write docs')] 3 [(2, 3, 'Test'), (3, 1, 'Write docs')] 4 [(3, 1, 'Write docs')] 5 [] while not queue.is_empty():
pass 1 of 473print("Custom priority queue:")74while not queue⟨PriorityQueue A⟩.is_empty():75 task, priority = queue⟨PriorityQueue A⟩.pop()76 print(f" Priority {priority}: {task}")self.heap ← [(1, 2, 'Deploy'), (2, 3, 'Test'), (3, 1, 'Write docs')]
pass 1 of 460def pop(self⟨PriorityQueue A⟩):61 priority→ 1, _→ 0, item→ Fix bug = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.heap→ [(1, 2, 'Deploy'), (2, 3, 'Test'), (3, 1, 'Write docs')])62 return itemFix bug, priority1All 4 passes — pass 1 is the card above pass self.heappriority_item1 [(1, 0, 'Fix bug'), (2, 3, 'Test'), (1, 2, 'Deploy'), (3, 1, 'Write docs')] → [(1, 2, 'Deploy'), (2, 3, 'Test'), (3, 1, 'Write docs')] 1 0 Fix bug 2 [(1, 2, 'Deploy'), (2, 3, 'Test'), (3, 1, 'Write docs')] → [(2, 3, 'Test'), (3, 1, 'Write docs')] 1 2 Deploy 3 [(2, 3, 'Test'), (3, 1, 'Write docs')] → [(3, 1, 'Write docs')] 2 3 Test 4 [(3, 1, 'Write docs')] → [] 3 1 Write docs task ← Fix bug, priority ← 1
74while not queue.is_empty():75 task→ Fix bug, priority→ 1 = queue⟨PriorityQueue A⟩.pop()76 print(f" Priority {priority1}: {taskFix bug}")output Priority 1: Fix bugtask ← Deploy, priority ← 1
74while not queue.is_empty():75 task→ Deploy, priority→ 1 = queue⟨PriorityQueue A⟩.pop()76 print(f" Priority {priority1}: {taskDeploy}")output Priority 1: Deploytask ← Test, priority ← 2
74while not queue.is_empty():75 task→ Test, priority→ 2 = queue⟨PriorityQueue A⟩.pop()76 print(f" Priority {priority2}: {taskTest}")output Priority 2: Testtask ← Write docs, priority ← 3
74while not queue.is_empty():75 task→ Write docs, priority→ 3 = queue⟨PriorityQueue A⟩.pop()76 print(f" Priority {priority3}: {taskWrite docs}")output Priority 3: Write docsprint(" Task scheduler:")
78# Task scheduler79print("\nTask scheduler:")8081class TaskScheduler:82 def __init__(self):83 self.tasks = []84 85 def add_task(self, name, priority, duration):86 heapq.heappush(self.tasks, (priority, duration, name))87 88 def execute_all(self):89 total_time = 090 while self.tasks:91 priority, duration, name = heapq.heappop(self.tasks)92 print(f" Executing: {name} (priority={priority}, duration={duration})")93 total_time += duration94 return total_time9596scheduler = TaskScheduler()97scheduler.add_task("Backup database", 2, 30)output Task scheduler:self.tasks ← []
81class TaskScheduler:82 def __init__(self⟨TaskScheduler B⟩):83 self.tasks→ [] = []scheduler ← ⟨TaskScheduler B⟩
96scheduler→ ⟨TaskScheduler B⟩ = TaskScheduler()97scheduler⟨TaskScheduler B⟩.add_task("Backup database", 2, 30)98scheduler.add_task("Deploy hotfix", 1, 15)self.tasks ← [(2, 30, 'Backup database')]
pass 1 of 485def add_task(self⟨TaskScheduler B⟩, nameBackup database, priority2, duration30):86 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.tasks→ [(2, 30, 'Backup database')], (priority2, duration30, nameBackup database))All 4 passes — pass 1 is the card above pass nameprioritydurationself.tasks1 Backup database 2 30 [] → [(2, 30, 'Backup database')] 2 Deploy hotfix 1 15 [(2, 30, 'Backup database')] → [(1, 15, 'Deploy hotfix'), (2, 30, 'Backup database')] 3 Update docs 3 45 [(1, 15, 'Deploy hotfix'), (2, 30, 'Backup database')] → [(1, 15, 'Deploy hotfix'), (2, 30, 'Backup database'), (3, 45, 'Update docs')] 4 Security patch 1 20 [(1, 15, 'Deploy hotfix'), (2, 30, 'Backup database'), (3, 45, 'Update docs')] → [(1, 15, 'Deploy hotfix'), (1, 20, 'Security patch'), (3, 45, 'Update docs'), (2, 30, 'Backup database')] scheduler.add_task("Backup database", 2, 30)
96scheduler = TaskScheduler()97scheduler⟨TaskScheduler B⟩.add_task("Backup database", 2, 30)98scheduler⟨TaskScheduler B⟩.add_task("Deploy hotfix", 1, 15)99scheduler.add_task("Update docs", 3, 45)scheduler.add_task("Deploy hotfix", 1, 15)
97scheduler.add_task("Backup database", 2, 30)98scheduler⟨TaskScheduler B⟩.add_task("Deploy hotfix", 1, 15)99scheduler⟨TaskScheduler B⟩.add_task("Update docs", 3, 45)100scheduler.add_task("Security patch", 1, 20)scheduler.add_task("Update docs", 3, 45)
98scheduler.add_task("Deploy hotfix", 1, 15)99scheduler⟨TaskScheduler B⟩.add_task("Update docs", 3, 45)100scheduler⟨TaskScheduler B⟩.add_task("Security patch", 1, 20)scheduler.add_task("Security patch", 1, 20)
99scheduler.add_task("Update docs", 3, 45)100scheduler⟨TaskScheduler B⟩.add_task("Security patch", 1, 20)101102print("Task execution order:")103total = scheduler⟨TaskScheduler B⟩.execute_all()104print(f"Total time: {total} minutes")outputTask execution order:total_time ← 0
88def execute_all(self⟨TaskScheduler B⟩):89 total_time→ 0 = 090 while self.tasks:self.tasks ← [(1, 20, 'Security patch'), (2, 30, 'Backup database'), (3, 45, 'Update docs')]
pass 1 of 489total_time = 090while self.tasks[(1, 15, 'Deploy hotfix'), (1, 20, 'Security patch'), (3, 45, 'Update docs'), (2, 30, 'Backup database')]:91 priority→ 1, duration→ 15, name→ Deploy hotfix = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.tasks→ [(1, 20, 'Security patch'), (2, 30, 'Backup database'), (3, 45, 'Update docs')])92 print(f" Executing: {nameDeploy hotfix} (priority={priority1}, duration={duration15})")93 total_time→ 15 += duration1594return total_timeoutput Executing: Deploy hotfix (priority=1, duration=15)All 4 passes — pass 1 is the card above pass self.tasksprioritydurationnametotal_time1 [(1, 15, 'Deploy hotfix'), (1, 20, 'Security patch'), (3, 45, 'Update docs'), (2, 30, 'Backup database')] → [(1, 20, 'Security patch'), (2, 30, 'Backup database'), (3, 45, 'Update docs')] 1 15 Deploy hotfix 0 → 15 2 [(1, 20, 'Security patch'), (2, 30, 'Backup database'), (3, 45, 'Update docs')] → [(2, 30, 'Backup database'), (3, 45, 'Update docs')] 1 20 Security patch 15 → 35 3 [(2, 30, 'Backup database'), (3, 45, 'Update docs')] → [(3, 45, 'Update docs')] 2 30 Backup database 35 → 65 4 [(3, 45, 'Update docs')] → [] 3 45 Update docs 65 → 110 return total_time
93 total_time += duration94return total_time110total ← 110
102print("Task execution order:")103total→ 110 = scheduler⟨TaskScheduler B⟩.execute_all()104print(f"Total time: {total110} minutes")105106# Event simulator107print("\nEvent simulator:")108109class Event:110 def __init__(self, time, event_type, handler):111 self.time = time112 self.event_type = event_type113 self.handler = handler114 115 def __lt__(self, other):116 return self.time < other.time117 118 def execute(self):119 return self.handler()120121class EventSimulator:122 def __init__(self):123 self.events = []124 self.current_time = 0125 126 def schedule(self, delay, event_type, handler):127 event = Event(self.current_time + delay, event_type, handler)128 heapq.heappush(self.events, event)129 130 def run(self):131 while self.events:132 event = heapq.heappop(self.events)133 self.current_time = event.time134 print(f"t={self.current_time}: {event.event_type}")135 event.execute()136137sim = EventSimulator()138sim.schedule(10, "Login", lambda: None)outputTotal time: 110 minutes Event simulator:self.events ← [], self.current_time ← 0
121class EventSimulator:122 def __init__(self⟨EventSimulator C⟩):123 self.events→ [] = []124 self.current_time→ 0 = 0sim ← ⟨EventSimulator C⟩
137sim→ ⟨EventSimulator C⟩ = EventSimulator()138sim⟨EventSimulator C⟩.schedule(10, "Login", lambda: None)139sim.schedule(5, "Page load", lambda: None)def schedule(self, delay, event_type, handler):
pass 1 of 4126def schedule(self⟨EventSimulator C⟩, delay10, event_typeLogin, handler<function <lambda> at ⟨addr D⟩>):127 event = Event(self.current_time0 + delay10, event_typeLogin, handler<function <lambda> at ⟨addr D⟩>)128 heapq.heappush(self.events, event)All 4 passes — pass 1 is the card above pass delayevent_typehandler1 10 Login <function <lambda> at ⟨addr D⟩> 2 5 Page load <function <lambda> at ⟨addr E⟩> 3 15 Click button <function <lambda> at ⟨addr F⟩> 4 8 Fetch data <function <lambda> at ⟨addr G⟩> self.time ← 10, self.event_type ← Login, self.handler ← <function <lambda> at ⟨addr D⟩>
pass 1 of 4109class Event:110 def __init__(self⟨Event H⟩, time10, event_typeLogin, handler<function <lambda> at ⟨addr D⟩>):111 self.time→ 10 = time10112 self.event_type→ Login = event_typeLogin113 self.handler→ <function <lambda> at ⟨addr D⟩> = handler<function <lambda> at ⟨addr D⟩>All 4 passes — pass 1 is the card above pass selftimeevent_typehandlerself.timeself.event_typeself.handler1 ⟨Event H⟩ 10 Login <function <lambda> at ⟨addr D⟩> 10 Login <function <lambda> at ⟨addr D⟩> 2 ⟨Event I⟩ 5 Page load <function <lambda> at ⟨addr E⟩> 5 Page load <function <lambda> at ⟨addr E⟩> 3 ⟨Event J⟩ 15 Click button <function <lambda> at ⟨addr F⟩> 15 Click button <function <lambda> at ⟨addr F⟩> 4 ⟨Event K⟩ 8 Fetch data <function <lambda> at ⟨addr G⟩> 8 Fetch data <function <lambda> at ⟨addr G⟩> event ← ⟨Event H⟩, self.events ← [⟨Event H⟩]
126def schedule(self, delay, event_type, handler):127 event→ ⟨Event H⟩ = Event(self.current_time0 + delay10, event_typeLogin, handler<function <lambda> at ⟨addr D⟩>)128 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events→ [⟨Event H⟩], event⟨Event H⟩)sim.schedule(10, "Login", lambda: None)
137sim = EventSimulator()138sim⟨EventSimulator C⟩.schedule(10, "Login", lambda: None)139sim⟨EventSimulator C⟩.schedule(5, "Page load", lambda: None)140sim.schedule(15, "Click button", lambda: None)event ← ⟨Event I⟩
126def schedule(self, delay, event_type, handler):127 event→ ⟨Event I⟩ = Event(self.current_time0 + delay5, event_typePage load, handler<function <lambda> at ⟨addr E⟩>)128 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events[⟨Event H⟩], event⟨Event I⟩)def __lt__(self, other):
pass 1 of 7115def __lt__(self⟨Event I⟩, other⟨Event H⟩):116 return self.time5 < other.time10All 7 passes — pass 1 is the card above pass selfotherself.timeother.time1 ⟨Event I⟩ ⟨Event H⟩ 5 10 2 ⟨Event J⟩ ⟨Event I⟩ 15 5 3 ⟨Event K⟩ ⟨Event H⟩ 8 10 4 ⟨Event K⟩ ⟨Event I⟩ 8 5 5 ⟨Event K⟩ ⟨Event J⟩ 8 15 6 ⟨Event H⟩ ⟨Event K⟩ 10 8 7 ⟨Event J⟩ ⟨Event H⟩ 15 10 self.events ← [⟨Event I⟩, ⟨Event H⟩]
127event = Event(self.current_time + delay, event_type, handler)128heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events→ [⟨Event I⟩, ⟨Event H⟩], event⟨Event I⟩)sim.schedule(5, "Page load", lambda: None)
138sim.schedule(10, "Login", lambda: None)139sim⟨EventSimulator C⟩.schedule(5, "Page load", lambda: None)140sim⟨EventSimulator C⟩.schedule(15, "Click button", lambda: None)141sim.schedule(8, "Fetch data", lambda: None)event ← ⟨Event J⟩
126def schedule(self, delay, event_type, handler):127 event→ ⟨Event J⟩ = Event(self.current_time0 + delay15, event_typeClick button, handler<function <lambda> at ⟨addr F⟩>)128 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events[⟨Event I⟩, ⟨Event H⟩], event⟨Event J⟩)self.events ← [⟨Event I⟩, ⟨Event H⟩, ⟨Event J⟩]
127event = Event(self.current_time + delay, event_type, handler)128heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events→ [⟨Event I⟩, ⟨Event H⟩, ⟨Event J⟩], event⟨Event J⟩)sim.schedule(15, "Click button", lambda: None)
139sim.schedule(5, "Page load", lambda: None)140sim⟨EventSimulator C⟩.schedule(15, "Click button", lambda: None)141sim⟨EventSimulator C⟩.schedule(8, "Fetch data", lambda: None)event ← ⟨Event K⟩
126def schedule(self, delay, event_type, handler):127 event→ ⟨Event K⟩ = Event(self.current_time0 + delay8, event_typeFetch data, handler<function <lambda> at ⟨addr G⟩>)128 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events[⟨Event I⟩, ⟨Event H⟩, ⟨Event J⟩], event⟨Event K⟩)self.events ← [⟨Event I⟩, ⟨Event K⟩, ⟨Event J⟩, ⟨Event H⟩]
127event = Event(self.current_time + delay, event_type, handler)128heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.events→ [⟨Event I⟩, ⟨Event K⟩, ⟨Event J⟩, ⟨Event H⟩], event⟨Event K⟩)sim.schedule(8, "Fetch data", lambda: None)
140sim.schedule(15, "Click button", lambda: None)141sim⟨EventSimulator C⟩.schedule(8, "Fetch data", lambda: None)142143print("Event simulation:")144sim⟨EventSimulator C⟩.run()outputEvent simulation:def run(self):
130def run(self⟨EventSimulator C⟩):131 while self.events:132 event = heapq.heappop(self.events)while self.events:
pass 1 of 4130def run(self):131 while self.events[⟨Event I⟩, ⟨Event K⟩, ⟨Event J⟩, ⟨Event H⟩]:132 event = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.events[⟨Event I⟩, ⟨Event K⟩, ⟨Event J⟩, ⟨Event H⟩])133 self.current_time = event.timeAll 4 passes — pass 1 is the card above pass event.timeevent.event_typeself.eventseventself.current_time1 — — [⟨Event I⟩, ⟨Event K⟩, ⟨Event J⟩, ⟨Event H⟩] — — 2 — — [⟨Event K⟩, ⟨Event H⟩, ⟨Event J⟩] — — 3 10 Login [⟨Event H⟩, ⟨Event J⟩] → [⟨Event J⟩] ⟨Event H⟩ 10 4 15 Click button [⟨Event J⟩] → [] ⟨Event J⟩ 15 self.events ← [⟨Event K⟩, ⟨Event H⟩, ⟨Event J⟩], event ← ⟨Event I⟩
131while self.events:132 event→ ⟨Event I⟩ = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.events→ [⟨Event K⟩, ⟨Event H⟩, ⟨Event J⟩])133 self.current_time→ 5 = event.time5134 print(f"t={self.current_time5}: {event.event_typePage load}")135 event⟨Event I⟩.execute()outputt=5: Page loaddef execute(self):
pass 1 of 4118def execute(self⟨Event I⟩):119 return self.handler()All 4 passes — pass 1 is the card above pass self1 ⟨Event I⟩ 2 ⟨Event K⟩ 3 ⟨Event H⟩ 4 ⟨Event J⟩ event.execute()
134print(f"t={self.current_time}: {event.event_type}")135event⟨Event I⟩.execute()self.events ← [⟨Event H⟩, ⟨Event J⟩], event ← ⟨Event K⟩, self.current_time ← 8
131while self.events:132 event→ ⟨Event K⟩ = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.events→ [⟨Event H⟩, ⟨Event J⟩])133 self.current_time→ 8 = event.time8134 print(f"t={self.current_time8}: {event.event_typeFetch data}")135 event⟨Event K⟩.execute()outputt=8: Fetch dataevent.execute()
134print(f"t={self.current_time}: {event.event_type}")135event⟨Event K⟩.execute()event.execute()
134print(f"t={self.current_time}: {event.event_type}")135event⟨Event H⟩.execute()event.execute()
134print(f"t={self.current_time}: {event.event_type}")135event⟨Event J⟩.execute()graph ← {'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []}
143print("Event simulation:")144sim⟨EventSimulator C⟩.run()145146# Dijkstra's algorithm147print("\nDijkstra's algorithm:")148149def dijkstra(graph, start):150 """Find shortest paths from start to all nodes"""151 distances = {node: float('inf') for node in graph}152 distances[start] = 0153 pq = [(0, start)]154 155 while pq:156 current_dist, current_node = heapq.heappop(pq)157 158 # Skip if we found a better path already159 if current_dist > distances[current_node]:160 continue161 162 for neighbor, weight in graph[current_node]:163 distance = current_dist + weight164 165 if distance < distances[neighbor]:166 distances[neighbor] = distance167 heapq.heappush(pq, (distance, neighbor))168 169 return distances170171graph→ {'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []} = {172 'A': [('B', 4), ('C', 2)],173 'B': [('D', 3)],174 'C': [('B', 1), ('D', 5)],175 'D': []176}177178distances = dijkstra(graph{'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []}, 'A')179print("Shortest distances from A:")output Dijkstra's algorithm:distances ← {'A': inf, 'B': inf, 'C': inf, 'D': inf}, distances[start] ← 0
149def dijkstra(graph{'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []}, startA):150 """Find shortest paths from start to all nodes"""151 distances→ {'A': inf, 'B': inf, 'C': inf, 'D': inf} = {node: float('inf') for node in graph{'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []}}152 distances[start]→ 0 = 0153 pq→ [(0, 'A')] = [(0, startA)]pq ← [], current_dist ← 0, current_node ← A
pass 1 of 6155while pq[(0, 'A')]:156 current_dist→ 0, current_node→ A = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(pq→ [])All 6 passes — pass 1 is the card above pass distances[current_node]pqcurrent_distcurrent_node1 — [(0, 'A')] → [] 0 A 2 — [(2, 'C'), (4, 'B')] → [(4, 'B')] 2 C 3 — [(3, 'B'), (4, 'B'), (7, 'D')] → [(4, 'B'), (7, 'D')] 3 B 4 3 [(4, 'B'), (7, 'D'), (6, 'D')] → [(6, 'D'), (7, 'D')] 4 B 5 — [(6, 'D'), (7, 'D')] → [(7, 'D')] 6 D 6 6 [(7, 'D')] → [] 7 D distance ← 4
pass 1 of 5162for neighborB, weight4 in graph[current_node][('B', 4), ('C', 2)]:163 distance→ 4 = current_dist0 + weight4All 5 passes — pass 1 is the card above pass neighborweightgraph[current_node]current_distdistances[current_node]distance1 B 4 [('B', 4), ('C', 2)] 0 — 4 2 C 2 [('B', 4), ('C', 2)] 0 — 2 3 B 1 [('B', 1), ('D', 5)] 2 — 3 4 D 5 [('B', 1), ('D', 5)] 2 — 7 5 D 3 [('D', 3)] 3 3 6 distances[neighbor] ← 4, pq ← [(4, 'B')]
pass 1 of 5165if distance4 < distances[neighbor]inf:166 distances[neighbor]→ 4 = distance4167 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(pq→ [(4, 'B')], (distance4, neighborB))All 5 passes — pass 1 is the card above pass distanceneighborcurrent_distdistances[current_node]distances[neighbor]pq1 4 B — — inf → 4 [] → [(4, 'B')] 2 2 C — — inf → 2 [(4, 'B')] → [(2, 'C'), (4, 'B')] 3 3 B — — 4 → 3 [(4, 'B')] → [(3, 'B'), (4, 'B')] 4 7 D — — inf → 7 [(3, 'B'), (4, 'B')] → [(3, 'B'), (4, 'B'), (7, 'D')] 5 6 D 4 3 7 → 6 [(4, 'B'), (7, 'D')] → [(4, 'B'), (7, 'D'), (6, 'D')] if current_dist > distances[current_node]:
pass 1 of 2158# Skip if we found a better path already159if current_dist4 > distances[current_node]3:160 continueif current_dist > distances[current_node]:
pass 2 of 2158# Skip if we found a better path already159if current_dist7 > distances[current_node]6:160 continuereturn distances
169return distances{'A': 0, 'B': 3, 'C': 2, 'D': 6}distances ← {'A': 0, 'B': 3, 'C': 2, 'D': 6}
178distances→ {'A': 0, 'B': 3, 'C': 2, 'D': 6} = dijkstra(graph{'A': [('B', 4), ('C', 2)], 'B': [('D', 3)], 'C': [('B', 1), ('D', 5)], 'D': []}, 'A')179print("Shortest distances from A:")180for node, dist in sorted(distances.items()):outputShortest distances from A:for node, dist in sorted(distances.items()):
pass 1 of 4179print("Shortest distances from A:")180for nodeA, dist0 in sorted(distances{'A': 0, 'B': 3, 'C': 2, 'D': 6}.items()):181 print(f" to {nodeA}: {dist0}")output to A: 0All 4 passes — pass 1 is the card above pass nodedist1 A 0 2 B 3 3 C 2 4 D 6 print(" Job queue:")
183# Job queue184print("\nJob queue:")185186class Job:187 def __init__(self, job_id, priority, name):188 self.id = job_id189 self.priority = priority190 self.name = name191 192 def __lt__(self, other):193 # Lower priority number = higher priority194 if self.priority != other.priority:195 return self.priority < other.priority196 return self.id < other.id197 198 def __repr__(self):199 return f"Job({self.id}, p={self.priority}, '{self.name}')"200201class JobQueue:202 def __init__(self):203 self.queue = []204 205 def add_job(self, job):206 heapq.heappush(self.queue, job)207 208 def get_next(self):209 return heapq.heappop(self.queue) if self.queue else None210 211 def size(self):212 return len(self.queue)213214jq = JobQueue()215jq.add_job(Job(1, 2, "Process data"))output Job queue:self.queue ← []
201class JobQueue:202 def __init__(self⟨JobQueue L⟩):203 self.queue→ [] = []jq ← ⟨JobQueue L⟩
214jq→ ⟨JobQueue L⟩ = JobQueue()215jq⟨JobQueue L⟩.add_job(Job(1, 2, "Process data"))216jq.add_job(Job(2, 1, "Critical update"))self.id ← 1, self.priority ← 2, self.name ← Process data
pass 1 of 4186class Job:187 def __init__(self(empty), job_id1, priority2, nameProcess data):188 self.id→ 1 = job_id1189 self.priority→ 2 = priority2190 self.name→ Process data = nameProcess dataAll 4 passes — pass 1 is the card above pass job_idprioritynameself.idself.priorityself.name1 1 2 Process data 1 2 Process data 2 2 1 Critical update 2 1 Critical update 3 3 3 Send emails 3 3 Send emails 4 4 1 Security scan 4 1 Security scan self.queue ← [Job(1, p=2, 'Process data')]
pass 1 of 4205def add_job(self⟨JobQueue L⟩, jobJob(1, p=2, 'Process data')):206 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.queue→ [Job(1, p=2, 'Process data')], jobJob(1, p=2, 'Process data'))All 4 passes — pass 1 is the card above pass jobself.queue1 Job(1, p=2, 'Process data') [] → [Job(1, p=2, 'Process data')] 2 Job(2, p=1, 'Critical update') [Job(1, p=2, 'Process data')] 3 Job(3, p=3, 'Send emails') [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data')] 4 Job(4, p=1, 'Security scan') [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data'), Job(3, p=3, 'Send emails')] jq.add_job(Job(1, 2, "Process data"))
214jq = JobQueue()215jq⟨JobQueue L⟩.add_job(Job(1, 2, "Process data"))216jq⟨JobQueue L⟩.add_job(Job(2, 1, "Critical update"))217jq.add_job(Job(3, 3, "Send emails"))def __lt__(self, other): # Lower priority number = higher prio…
pass 1 of 7192def __lt__(selfJob(2, p=1, 'Critical update'), otherJob(1, p=2, 'Process data')):193 # Lower priority number = higher priority194 if self.priority != other.priority:195 return self.priority < other.priorityAll 7 passes — pass 1 is the card above pass selfotherself.idother.id1 Job(2, p=1, 'Critical update') Job(1, p=2, 'Process data') — — 2 Job(3, p=3, 'Send emails') Job(2, p=1, 'Critical update') — — 3 Job(4, p=1, 'Security scan') Job(1, p=2, 'Process data') — — 4 Job(4, p=1, 'Security scan') Job(2, p=1, 'Critical update') 4 2 5 Job(4, p=1, 'Security scan') Job(3, p=3, 'Send emails') — — 6 Job(1, p=2, 'Process data') Job(4, p=1, 'Security scan') — — 7 Job(3, p=3, 'Send emails') Job(1, p=2, 'Process data') — — if self.priority != other.priority:
pass 1 of 6193# Lower priority number = higher priority194if self.priority1 != other.priority2:195 return self.priority1 < other.priority2196return self.id < other.idAll 6 passes — pass 1 is the card above pass self.priorityother.priority1 1 2 2 3 1 3 1 2 4 1 3 5 2 1 6 3 2 self.queue ← [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data')]
205def add_job(self, job):206 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.queue→ [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data')], jobJob(2, p=1, 'Critical update'))jq.add_job(Job(2, 1, "Critical update"))
215jq.add_job(Job(1, 2, "Process data"))216jq⟨JobQueue L⟩.add_job(Job(2, 1, "Critical update"))217jq⟨JobQueue L⟩.add_job(Job(3, 3, "Send emails"))218jq.add_job(Job(4, 1, "Security scan"))self.queue ← [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data'), Job(3, p=3, 'Send emails')]
205def add_job(self, job):206 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.queue→ [Job(2, p=1, 'Critical update'), Job(1, p=2, 'Process data'), Job(3, p=3, 'Send emails')], jobJob(3, p=3, 'Send emails'))jq.add_job(Job(3, 3, "Send emails"))
216jq.add_job(Job(2, 1, "Critical update"))217jq⟨JobQueue L⟩.add_job(Job(3, 3, "Send emails"))218jq⟨JobQueue L⟩.add_job(Job(4, 1, "Security scan"))self.queue ← [Job(2, p=1, 'Critical update'), Job(4, p=1, 'Security scan'), Job(3, p=3, 'Send emails'), Job(1, p=2, 'Process data')]
205def add_job(self, job):206 heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(self.queue→ [Job(2, p=1, 'Critical update'), Job(4, p=1, 'Security scan'), Job(3, p=3, 'Send emails'), Job(1, p=2, 'Process data')], jobJob(4, p=1, 'Security scan'))jq.add_job(Job(4, 1, "Security scan"))
217jq.add_job(Job(3, 3, "Send emails"))218jq⟨JobQueue L⟩.add_job(Job(4, 1, "Security scan"))219220print(f"Job queue size: {jq⟨JobQueue L⟩.size()}")221print("Processing jobs:")def size(self):
211def size(self⟨JobQueue L⟩):212 return len(self.queue[Job(2, p=1, 'Critical update'), Job(4, p=1, 'Security scan'), Job(3, p=3, 'Send emails'), Job(1, p=2, 'Process data')])print(f"Job queue size: {jq.size()}")
220print(f"Job queue size: {jq⟨JobQueue L⟩.size()}")221print("Processing jobs:")222while job := jq.get_next():outputJob queue size: 4 Processing jobs:def get_next(self):
pass 1 of 5208def get_next(self⟨JobQueue L⟩):209 return heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(self.queue[Job(2, p=1, 'Critical update'), Job(4, p=1, 'Security scan'), Job(3, p=3, 'Send emails'), Job(1, p=2, 'Process data')]) if self.queue else NoneAll 5 passes — pass 1 is the card above pass self.queue1 [Job(2, p=1, 'Critical update'), Job(4, p=1, 'Security scan'), Job(3, p=3, 'Send emails'), Job(1, p=2, 'Process data')] 2 [Job(4, p=1, 'Security scan'), Job(1, p=2, 'Process data'), Job(3, p=3, 'Send emails')] 3 [Job(1, p=2, 'Process data'), Job(3, p=3, 'Send emails')] 4 [Job(3, p=3, 'Send emails')] 5 [] while job := jq.get_next():
pass 1 of 4221print("Processing jobs:")222while jobJob(2, p=1, 'Critical update') := jq⟨JobQueue L⟩.get_next():223 print(f" {jobJob(2, p=1, 'Critical update')}")output Job(2, p=1, 'Critical update')All 4 passes — pass 1 is the card above pass job1 Job(2, p=1, 'Critical update') 2 Job(4, p=1, 'Security scan') 3 Job(1, p=2, 'Process data') 4 Job(3, p=3, 'Send emails') connections ← []
225# Bandwidth allocation226print("\nBandwidth allocation:")227228class Connection:229 def __init__(self, user, priority, bandwidth):230 self.user = user231 self.priority = priority232 self.bandwidth = bandwidth233 234 def __lt__(self, other):235 return self.priority < other.priority236237connections→ [] = []238heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections[], Connection("user1", 2, 100))239heapq.heappush(connections, Connection("user2", 1, 50))output Bandwidth allocation:self.user ← user1, self.priority ← 2, self.bandwidth ← 100
pass 1 of 4228class Connection:229 def __init__(self⟨Connection I⟩, useruser1, priority2, bandwidth100):230 self.user→ user1 = useruser1231 self.priority→ 2 = priority2232 self.bandwidth→ 100 = bandwidth100All 4 passes — pass 1 is the card above pass selfuserprioritybandwidthself.userself.priorityself.bandwidth1 ⟨Connection I⟩ user1 2 100 user1 2 100 2 ⟨Connection M⟩ user2 1 50 user2 1 50 3 ⟨Connection N⟩ user3 3 75 user3 3 75 4 ⟨Connection O⟩ user4 1 25 user4 1 25 connections ← [⟨Connection I⟩]
237connections = []238heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections→ [⟨Connection I⟩], Connection("user1", 2, 100))239heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections[⟨Connection I⟩], Connection("user2", 1, 50))240heapq.heappush(connections, Connection("user3", 3, 75))def __lt__(self, other):
pass 1 of 7234def __lt__(self⟨Connection M⟩, other⟨Connection I⟩):235 return self.priority1 < other.priority2All 7 passes — pass 1 is the card above pass selfotherself.priorityother.priority1 ⟨Connection M⟩ ⟨Connection I⟩ 1 2 2 ⟨Connection N⟩ ⟨Connection M⟩ 3 1 3 ⟨Connection O⟩ ⟨Connection I⟩ 1 2 4 ⟨Connection O⟩ ⟨Connection M⟩ 1 1 5 ⟨Connection O⟩ ⟨Connection N⟩ 1 3 6 ⟨Connection I⟩ ⟨Connection O⟩ 2 1 7 ⟨Connection N⟩ ⟨Connection I⟩ 3 2 connections ← [⟨Connection M⟩, ⟨Connection I⟩]
238heapq.heappush(connections, Connection("user1", 2, 100))239heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections→ [⟨Connection M⟩, ⟨Connection I⟩], Connection("user2", 1, 50))240heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections[⟨Connection M⟩, ⟨Connection I⟩], Connection("user3", 3, 75))241heapq.heappush(connections, Connection("user4", 1, 25))connections ← [⟨Connection M⟩, ⟨Connection I⟩, ⟨Connection N⟩]
239heapq.heappush(connections, Connection("user2", 1, 50))240heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections→ [⟨Connection M⟩, ⟨Connection I⟩, ⟨Connection N⟩], Connection("user3", 3, 75))241heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections[⟨Connection M⟩, ⟨Connection I⟩, ⟨Connection N⟩], Connection("user4", 1, 25))connections ← [⟨Connection M⟩, ⟨Connection O⟩, ⟨Connection N⟩, ⟨Connection I⟩]
240heapq.heappush(connections, Connection("user3", 3, 75))241heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappush(connections→ [⟨Connection M⟩, ⟨Connection O⟩, ⟨Connection N⟩, ⟨Connection I⟩], Connection("user4", 1, 25))242243total_bandwidth→ 200 = 200244allocated→ 0 = 0245246print("Allocating bandwidth:")247while connections and allocated < total_bandwidth:outputAllocating bandwidth:while connections and allocated < total_bandwidth:
pass 1 of 4246print("Allocating bandwidth:")247while connections[⟨Connection M⟩, ⟨Connection O⟩, ⟨Connection N⟩, ⟨Connection I⟩] and allocated0 < total_bandwidth200:248 conn = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(connections[⟨Connection M⟩, ⟨Connection O⟩, ⟨Connection N⟩, ⟨Connection I⟩])249 if allocated + conn.bandwidth <= total_bandwidth:All 4 passes — pass 1 is the card above pass conn.userconn.priorityconnectionsconnremainingallocated1 — — [⟨Connection M⟩, ⟨Connection O⟩, ⟨Connection N⟩, ⟨Connection I⟩] — — 0 2 — — [⟨Connection O⟩, ⟨Connection I⟩, ⟨Connection N⟩] — — 50 3 — — [⟨Connection I⟩, ⟨Connection N⟩] → [⟨Connection N⟩] ⟨Connection I⟩ — 75 4 user3 3 [⟨Connection N⟩] → [] ⟨Connection N⟩ 25 175 → 200 connections ← [⟨Connection O⟩, ⟨Connection I⟩, ⟨Connection N⟩]
247while connections and allocated < total_bandwidth:248 conn→ ⟨Connection M⟩ = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(connections→ [⟨Connection O⟩, ⟨Connection I⟩, ⟨Connection N⟩])249 if allocated + conn.bandwidth <= total_bandwidth:allocated ← 50
pass 1 of 3248conn = heapq.heappop(connections)249if allocated0 + conn.bandwidth50 <= total_bandwidth200:250 print(f" {conn.useruser2}: {conn.bandwidth50} MB/s (priority {conn.priority1})")251 allocated→ 50 += conn.bandwidth50252else:output user2: 50 MB/s (priority 1)All 3 passes — pass 1 is the card above pass conn.bandwidthconn.userconn.priorityallocatedremaining1 50 user2 1 0 → 50 — 2 25 user4 1 50 → 75 — 3 100 user1 2 75 → 175 25 connections ← [⟨Connection I⟩, ⟨Connection N⟩], conn ← ⟨Connection O⟩
247while connections and allocated < total_bandwidth:248 conn→ ⟨Connection O⟩ = heapq<module 'heapq' from '/usr/local/lib/python3.12/heapq.py'>.heappop(connections→ [⟨Connection I⟩, ⟨Connection N⟩])249 if allocated + conn.bandwidth <= total_bandwidth:remaining ← 25, allocated ← 200
250 print(f" {conn.user}: {conn.bandwidth} MB/s (priority {conn.priority})")251 allocated += conn.bandwidth252else:253 remaining→ 25 = total_bandwidth200 - allocated175254 print(f" {conn.useruser3}: {remaining25} MB/s (partial, priority {conn.priority3})")255 allocated→ 200 = total_bandwidth200output user3: 25 MB/s (partial, priority 3)
priority queue
A data structure where elements are retrieved in priority order rather than insertion order - implemented efficiently using heaps.
Exercise: practical.py
Implement a task scheduler that processes jobs by priority and deadline