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.

Priority Queue Pattern

Using heaps for task scheduling:

bisect.py 
"""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 = 

# 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 = 

# 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 = 

# 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}")
insort.py 
"""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 comparison
print("\nPerformance comparison:")

import time

# insort approach
start = time.time()
sorted_insort = []
data = list(range(80, 0, -1))
for num in data:
    bisect.insort(sorted_insort, num)
insort_time = time.time() - start

# sort approach
start = time.time()
sorted_sort = sorted(data)
sort_time = time.time() - start

print(f"insort time: {insort_time:.4f}s")
print(f"sorted() time: {sort_time:.4f}s")
print("Note: sorted() is faster for bulk operations")
print("      insort is better for incremental additions")
heappush_pop.py 
"""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}")
nlargest_nsmallest.py 
"""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}")
priority_queue.py 
"""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
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_left vs bisect_right bisect_left returns the leftmost position for equal values, bisect_right returns the rightmost - matters when duplicates exist.
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 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.
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