Min-Heap vs Max-Heap

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

import heapq
from typing import List, Any, TypeVar, Generic
 
T = TypeVar('T')
 
class MaxHeapViaNotation:
    """
    A max-heap implemented by negating values in Python's min-heap.
    
    This is the most common pattern in Python competitive programming
    and algorithm interviews.
    
    Advantages:
    - Simple, no external dependencies
    - Works with numbers directly
    - Minimal overhead
    
    Disadvantages:
    - Only works with numeric types
    - Easy to forget negation (bugs!)
    - Intrusive: callers may see negated values in errors/debugging
    """
    
    def __init__(self):
        self._heap: List[float] = []
    
    def push(self, value: float) -> None:
        """Insert a value. Time: O(log n)"""
        heapq.heappush(self._heap, -value)  # Negate on insert
    
    def pop(self) -> float:
        """Remove and return the maximum. Time: O(log n)"""
        return -heapq.heappop(self._heap)  # Negate on extract
    
    def peek(self) -> float:
        """Return the maximum without removing. Time: O(1)"""
        return -self._heap[0]  # Negate when peeking
    
    def __len__(self) -> int:
        return len(self._heap)
    
    def __bool__(self) -> bool:
        return bool(self._heap)
 
 
# Common patterns in interview/competitive programming context
def find_k_largest_negation(nums: List[int], k: int) -> List[int]:
    """
    Find k largest elements using negation.
    
    Strategy: Use min-heap of negated values = max-heap behavior
    Actually, for k largest, we use a min-heap of size k directly!
    This example shows negation for a different approach.
    """
    # Negate all values, use min-heap, extract k smallest (= k largest original)
    negated_heap = [-x for x in nums]
    heapq.heapify(negated_heap)
    
    result = []
    for _ in range(k):
        result.append(-heapq.heappop(negated_heap))
    
    return result
 
 
def kth_largest_stream(nums: List[int], k: int) -> int:
    """
    Find the kth largest element in a stream.
    This actually uses min-heap of size k (more efficient).
    Shown here: alternative with full max-heap.
    """
    # Full max-heap approach (less efficient but demonstrates negation)
    max_heap = [-x for x in nums]
    heapq.heapify(max_heap)
    
    # Pop k elements to get kth largest
    for _ in range(k - 1):
        heapq.heappop(max_heap)
    
    return -max_heap[0]
 
 
# Working with tuples: negate the comparison key
def priority_queue_max_heap_example():
    """
    Priority queue where higher priority value = more important.
    Tuples are compared element by element, so negate the first element.
    """
    tasks = []
    
    # Task format: (priority, task_name)
    # Higher priority should come first -> negate priority
    heapq.heappush(tasks, (-5, "critical_task"))
    heapq.heappush(tasks, (-1, "low_priority_task"))
    heapq.heappush(tasks, (-3, "medium_priority_task"))
    
    while tasks:
        neg_priority, task_name = heapq.heappop(tasks)
        actual_priority = -neg_priority
        print(f"Processing {task_name} with priority {actual_priority}")
    
    # Output:
    # Processing critical_task with priority 5
    # Processing medium_priority_task with priority 3
    # Processing low_priority_task with priority 1

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

from dataclasses import dataclass
from functools import total_ordering
import heapq
from typing import TypeVar, Generic, List, Any
 
T = TypeVar('T')
 
@total_ordering
class MaxHeapItem(Generic[T]):
    """
    Wrapper that reverses comparison for any comparable type.
    
    Using @total_ordering, we only need to define __eq__ and __lt__,
    and Python generates the other comparison operators.
    
    Advantages:
    - Works with any comparable type (strings, objects, etc.)
    - Type-safe: preserves original type in .value
    - Clear semantics: explicitly inverts comparison
    
    Disadvantages:
    - Memory overhead: each item wrapped in an object
    - Slight performance overhead: extra indirection
    - Boilerplate: need to wrap/unwrap values
    """
    __slots__ = ['value']  # Memory optimization
    
    def __init__(self, value: T):
        self.value = value
    
    def __eq__(self, other: 'MaxHeapItem[T]') -> bool:
        return self.value == other.value
    
    def __lt__(self, other: 'MaxHeapItem[T]') -> bool:
        # Reversed comparison: greater values are "less than" for heap ordering
        return self.value > other.value
    
    def __repr__(self) -> str:
        return f"MaxHeapItem({self.value!r})"
 
 
class MaxHeap(Generic[T]):
    """
    A clean max-heap interface using wrapper items.
    
    The wrapper approach is ideal when:
    - You need max-heap for non-numeric types
    - You want clean, readable code
    - Performance is not hyper-critical
    """
    
    def __init__(self, items: List[T] = None):
        self._heap: List[MaxHeapItem[T]] = []
        if items:
            self._heap = [MaxHeapItem(x) for x in items]
            heapq.heapify(self._heap)
    
    def push(self, value: T) -> None:
        """Insert value. Time: O(log n)"""
        heapq.heappush(self._heap, MaxHeapItem(value))
    
    def pop(self) -> T:
        """Remove and return maximum. Time: O(log n)"""
        return heapq.heappop(self._heap).value
    
    def peek(self) -> T:
        """Return maximum without removing. Time: O(1)"""
        return self._heap[0].value
    
    def __len__(self) -> int:
        return len(self._heap)
    
    def __bool__(self) -> bool:
        return bool(self._heap)
 
 
# Example: Max-heap of strings (by length, then lexicographically reversed)
@total_ordering
class MaxString:
    """Wrapper for strings where longer strings are 'smaller' in heap terms."""
    __slots__ = ['value']
    
    def __init__(self, value: str):
        self.value = value
    
    def __eq__(self, other: 'MaxString') -> bool:
        return self.value == other.value
    
    def __lt__(self, other: 'MaxString') -> bool:
        # Longer strings should come out first (be "smaller" for min-heap extraction)
        if len(self.value) != len(other.value):
            return len(self.value) > len(other.value)
        # For equal lengths, lexicographically later is "smaller"
        return self.value > other.value
    
    def __repr__(self) -> str:
        return f"MaxString({self.value!r})"
 
 
def longest_k_strings(strings: List[str], k: int) -> List[str]:
    """Find the k longest strings using a max-heap wrapper."""
    heap = [MaxString(s) for s in strings]
    heapq.heapify(heap)
    
    result = []
    for _ in range(min(k, len(heap))):
        result.append(heapq.heappop(heap).value)
    
    return result
 
 
# Generic reversed wrapper using key function
@total_ordering
class Reversed(Generic[T]):
    """
    Generic wrapper that reverses any comparable type's ordering.
    
    Usage:
        heap = []
        heapq.heappush(heap, Reversed(50))
        heapq.heappush(heap, Reversed(30))
        max_value = heapq.heappop(heap).value  # Returns 50
    """
    __slots__ = ['value']
    
    def __init__(self, value: T):
        self.value = value
    
    def __eq__(self, other: 'Reversed[T]') -> bool:
        if isinstance(other, Reversed):
            return self.value == other.value
        return NotImplemented
    
    def __lt__(self, other: 'Reversed[T]') -> bool:
        if isinstance(other, Reversed):
            return self.value > other.value  # Reversed!
        return NotImplemented
    
    def __repr__(self) -> str:
        return f"Reversed({self.value!r})"

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

// ==================== JAVA ====================
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Collections;
 
public class HeapConversions {
    
    public static void javaHeapConversions() {
        // Java's PriorityQueue is min-heap by default (natural ordering)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(3);
        System.out.println(minHeap.poll()); // 1 (minimum)
        
        // Convert to max-heap using reverseOrder comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(5);
        maxHeap.add(1);
        maxHeap.add(3);
        System.out.println(maxHeap.poll()); // 5 (maximum)
        
        // Custom comparator for complex types
        PriorityQueue<int[]> maxBySecondElement = new PriorityQueue<>(
            (a, b) -> Integer.compare(b[1], a[1])  // Descending by second element
        );
        maxBySecondElement.add(new int[]{1, 100});
        maxBySecondElement.add(new int[]{2, 50});
        maxBySecondElement.add(new int[]{3, 75});
        int[] top = maxBySecondElement.poll(); // {1, 100}
        
        // Lambda for max-heap of integers (alternative to reverseOrder)
        PriorityQueue<Integer> maxHeapLambda = new PriorityQueue<>((a, b) -> b - a);
        
        // Custom class with comparator
        class Task {
            String name;
            int priority;
            Task(String n, int p) { name = n; priority = p; }
        }
        
        // Max-heap by priority
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority).reversed()
        );
    }
}

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

// ==================== C++ ====================
#include <queue>
#include <vector>
#include <functional>
 
void cppHeapConversions() {
    // C++ priority_queue is MAX-heap by default
    std::priority_queue<int> maxHeap;
    maxHeap.push(5);
    maxHeap.push(1);
    maxHeap.push(3);
    // maxHeap.top() returns 5 (maximum)
    
    // Convert to min-heap using greater<>
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(3);
    // minHeap.top() returns 1 (minimum)
    
    // Custom comparator for complex types
    struct Task {
        std::string name;
        int priority;
        double deadline;
    };
    
    // Min-heap by deadline (earliest deadline first)
    auto cmpByDeadline = [](const Task& a, const Task& b) {
        return a.deadline > b.deadline;  // Note: > for min-heap behavior
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmpByDeadline)> 
        edfQueue(cmpByDeadline);
    
    // Max-heap by priority
    auto cmpByPriority = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // < for max-heap (default behavior)
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmpByPriority)> 
        priorityQueue(cmpByPriority);
    
    // Using a functor class for comparator
    struct TaskComparator {
        bool operator()(const Task& a, const Task& b) const {
            // Multi-level: priority first, then deadline
            if (a.priority != b.priority) {
                return a.priority < b.priority;  // Max-heap by priority
            }
            return a.deadline > b.deadline;  // Min-heap by deadline (tie-breaker)
        }
    };
    std::priority_queue<Task, std::vector<Task>, TaskComparator> customQueue;
}

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

// ==================== RUST ====================
use std::collections::BinaryHeap;
use std::cmp::Reverse;
 
fn rust_heap_conversions() {
    // Rust's BinaryHeap is MAX-heap by default
    let mut max_heap = BinaryHeap::new();
    max_heap.push(5);
    max_heap.push(1);
    max_heap.push(3);
    assert_eq!(max_heap.pop(), Some(5)); // Maximum
    
    // Convert to min-heap using Reverse wrapper
    let mut min_heap = BinaryHeap::new();
    min_heap.push(Reverse(5));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(3));
    assert_eq!(min_heap.pop(), Some(Reverse(1))); // Minimum (wrapped)
    
    // Custom types need Ord implementation
    #[derive(Eq, PartialEq)]
    struct Task {
        priority: i32,
        name: String,
    }
    
    // Implement Ord for max-heap by priority
    impl Ord for Task {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.priority.cmp(&other.priority)  // Natural: max-heap by priority
        }
    }
    
    impl PartialOrd for Task {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }
    
    // For min-heap behavior, wrap in Reverse:
    // min_task_heap.push(Reverse(task));
}
 
// ==================== GO ====================
// Go's container/heap requires implementing heap.Interface
 
/*
import "container/heap"
 
// IntMinHeap implements heap.Interface for min-heap of ints
type IntMinHeap []int
 
func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }  // Min-heap
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
func (h *IntMinHeap) Push(x any) {
    *h = append(*h, x.(int))
}
 
func (h *IntMinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 
// IntMaxHeap - just change Less to flip comparison
type IntMaxHeap []int
 
func (h IntMaxHeap) Less(i, j int) bool { return h[i] > h[j] }  // Max-heap
// ... rest same as IntMinHeap
*/

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

import heapq
from typing import List, Tuple, Any
 
"""
Tuple Comparison in Python:
- Tuples are compared element-by-element from left to right
- First differing element determines the ordering
- You can control ordering by:
  1. Negating numeric elements you want reversed
  2. Reordering elements to change comparison priority
  3. Adding tie-breaker elements
"""
 
# Example 1: Priority Queue with Max-Priority, FIFO fallback
def priority_queue_max_fifo():
    """
    Items: (priority, arrival_order, data)
    Want: Max priority first, FIFO for equal priority
    
    Solution: Negate priority, keep arrival_order positive
    """
    counter = 0
    queue = []
    
    def enqueue(priority: int, data: Any):
        nonlocal counter
        # Negate priority for max-heap; counter provides FIFO ordering
        heapq.heappush(queue, (-priority, counter, data))
        counter += 1
    
    def dequeue():
        neg_priority, _, data = heapq.heappop(queue)
        return (-neg_priority, data)  # Return actual priority
    
    # Test
    enqueue(1, "low-1")
    enqueue(3, "high-1")
    enqueue(1, "low-2")   # Same priority as low-1, should come after
    enqueue(3, "high-2")  # Same priority as high-1, should come after
    
    while queue:
        priority, data = dequeue()
        print(f"Priority {priority}: {data}")
    
    # Output:
    # Priority 3: high-1
    # Priority 3: high-2
    # Priority 1: low-1
    # Priority 1: low-2
 
 
# Example 2: Multi-Key Sorting with Mixed Directions
def process_orders_complex():
    """
    Orders: (urgency, value, timestamp)
    Want: 
    - Highest urgency first (descending)
    - Among equal urgency: highest value first (descending)
    - Among equal value: earliest timestamp first (ascending)
    
    Solution: Negate urgency and value; keep timestamp positive
    """
    orders = []
    
    def add_order(urgency: int, value: float, timestamp: float, order_id: str):
        # Negate urgency and value for descending; timestamp ascending
        heapq.heappush(orders, (-urgency, -value, timestamp, order_id))
    
    def get_next_order() -> Tuple[int, float, float, str]:
        neg_urg, neg_val, ts, order_id = heapq.heappop(orders)
        return (-neg_urg, -neg_val, ts, order_id)
    
    # Add some orders
    add_order(3, 100.0, 1.0, "A")  # High urgency, high value, earliest
    add_order(3, 100.0, 2.0, "B")  # Same urgency/value, later
    add_order(3, 50.0, 0.5, "C")   # Same urgency, lower value
    add_order(5, 10.0, 3.0, "D")   # Highest urgency
    
    while orders:
        urg, val, ts, oid = get_next_order()
        print(f"Order {oid}: urgency={urg}, value={val}, ts={ts}")
    
    # Output:
    # Order D: urgency=5, value=10.0, ts=3.0  (highest urgency)
    # Order A: urgency=3, value=100.0, ts=1.0  (next urgency, highest value, earlier)
    # Order B: urgency=3, value=100.0, ts=2.0  (same urgency/value, later timestamp)
    # Order C: urgency=3, value=50.0, ts=0.5  (same urgency, lower value)
 
 
# Example 3: Dijkstra with Tie-Breaking
def dijkstra_with_tiebreak(graph, start, end):
    """
    Standard Dijkstra finds shortest distance, but what if there are
    multiple paths of the same length? Add tie-breakers:
    - Primary: distance (ascending - min-heap default)
    - Secondary: number of edges (ascending - fewer hops preferred)
    - Tertiary: lexicographic order of path (for deterministic output)
    """
    import heapq
    
    # Heap entries: (distance, num_edges, node_id, path)
    # All in ascending order, so no negation needed
    heap = [(0, 0, start, [start])]
    visited = set()
    
    while heap:
        dist, edges, node, path = heapq.heappop(heap)
        
        if node in visited:
            continue
        visited.add(node)
        
        if node == end:
            return dist, edges, path
        
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(heap, (
                    dist + weight,    # Primary: distance
                    edges + 1,        # Secondary: edge count
                    neighbor,         # Tertiary: node ID (for determinism)
                    path + [neighbor] # Path tracking
                ))
    
    return float('inf'), 0, []
 
 
# Example 4: Handling Non-Comparable Elements
def heap_with_noncomparable():
    """
    Problem: You want to heap objects that aren't directly comparable.
    Solution: Use a tuple with comparable keys + a counter for tie-breaking.
    """
    
    class Task:
        # Tasks are NOT directly comparable
        def __init__(self, name: str, priority: int):
            self.name = name
            self.priority = priority
    
    counter = 0
    heap = []
    
    def push(task: Task):
        nonlocal counter
        # Tuple: (negated_priority, unique_counter, task)
        # Counter ensures no two entries ever need to compare the Task objects
        heapq.heappush(heap, (-task.priority, counter, task))
        counter += 1
    
    def pop() -> Task:
        return heapq.heappop(heap)[2]  # Return just the task
    
    # Usage
    push(Task("Task A", 1))
    push(Task("Task B", 3))  # Higher priority
    push(Task("Task C", 3))  # Same priority as B
    
    # Even though Task objects can't be compared, heapq works because
    # the counter breaks ties before Python tries to compare Tasks
    while heap:
        task = pop()
        print(f"{task.name} (priority {task.priority})")
    
    # Output:
    # Task B (priority 3)
    # Task C (priority 3)  <- Came after B due to counter
    # Task A (priority 1)

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

import heapq
from typing import List
 
def convert_min_to_max_heap(min_heap: List[int]) -> List[int]:
    """
    Convert a min-heap to a max-heap.
    
    There's no efficient in-place conversion. We must:
    Option 1: Extract all elements and reheapify (O(n log n))
    Option 2: Negate values and reheapify (O(n) with heapify)
    
    We use Option 2 for O(n) time complexity.
    """
    # Negate all values
    max_heap = [-x for x in min_heap]
    # Heapify with negated values (this is O(n))
    heapq.heapify(max_heap)
    return max_heap
 
 
def convert_max_to_min_heap(max_heap: List[int]) -> List[int]:
    """
    Convert a max-heap (stored as negated values) to a proper min-heap.
    
    If the max-heap was implemented via negation, un-negate and heapify.
    """
    # Un-negate all values
    min_heap = [-x for x in max_heap]
    # Heapify as normal min-heap
    heapq.heapify(min_heap)
    return min_heap
 
 
def convert_heap_with_new_criterion(heap: List[tuple], new_key_index: int) -> List[tuple]:
    """
    Convert a heap to use a different comparison key.
    
    Example: Heap was sorted by first element, now sort by second element.
    This requires full rebuild.
    
    Time Complexity: O(n) for heapify after restructuring
    """
    # Create new tuples with the desired key first (for min-heap behavior)
    # This is a simplified example; real cases may need more transformation
    reordered = [(item[new_key_index], *item) for item in heap]
    heapq.heapify(reordered)
    return reordered
 
 
# Example: Switching between different priority criteria
class AdaptiveHeap:
    """
    A heap that can switch between min and max behavior.
    
    Warning: Switching has O(n) cost. Only use when switches are rare.
    """
    
    def __init__(self, is_max_heap: bool = False):
        self._heap: List[int] = []
        self._is_max_heap = is_max_heap
    
    def push(self, value: int) -> None:
        if self._is_max_heap:
            heapq.heappush(self._heap, -value)
        else:
            heapq.heappush(self._heap, value)
    
    def pop(self) -> int:
        value = heapq.heappop(self._heap)
        return -value if self._is_max_heap else value
    
    def peek(self) -> int:
        value = self._heap[0]
        return -value if self._is_max_heap else value
    
    def switch_mode(self) -> None:
        """
        Switch between min-heap and max-heap mode.
        Time Complexity: O(n)
        """
        # Un-negate if currently max-heap, negate if currently min-heap
        self._heap = [-x for x in self._heap]
        heapq.heapify(self._heap)
        self._is_max_heap = not self._is_max_heap
    
    def __len__(self) -> int:
        return len(self._heap)
 
 
# Demonstration
def demo_heap_conversion():
    # Start with min-heap
    min_heap = [1, 3, 2, 7, 5, 4, 6]
    heapq.heapify(min_heap)
    print(f"Min-heap: {min_heap}, min = {min_heap[0]}")
    
    # Convert to max-heap
    max_heap = convert_min_to_max_heap(min_heap)
    print(f"Max-heap (negated): {max_heap}, max = {-max_heap[0]}")
    
    # Use adaptive heap
    adaptive = AdaptiveHeap(is_max_heap=False)
    for val in [5, 2, 8, 1, 9]:
        adaptive.push(val)
    
    print(f"Adaptive (min mode): peek = {adaptive.peek()}")
    adaptive.switch_mode()
    print(f"Adaptive (max mode): peek = {adaptive.peek()}")

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

"""
Best Practice: Production-Quality Max-Heap Wrapper
 
This demonstrates the recommended approach for a reusable max-heap
in Python: encapsulated, type-hinted, well-documented, and tested.
"""
from __future__ import annotations
import heapq
from typing import TypeVar, Generic, List, Optional, Callable, Iterator
from dataclasses import dataclass
 
T = TypeVar('T')
K = TypeVar('K')  # Key type for comparison
 
@dataclass
class HeapItem(Generic[T, K]):
    """Internal representation of a heap item with its comparison key."""
    key: K
    value: T
    insertion_order: int
    
    def __lt__(self, other: HeapItem[T, K]) -> bool:
        if self.key != other.key:
            return self.key < other.key
        return self.insertion_order < other.insertion_order
 
 
class MaxHeap(Generic[T]):
    """
    A production-quality max-heap implementation for Python.
    
    Features:
    - Works with any type (numbers, strings, objects)
    - Optional key function for custom ordering
    - Stable ordering for equal elements (FIFO)
    - Type-hinted for IDE support
    - Comprehensive edge case handling
    
    Example:
        # Simple usage with numbers
        heap = MaxHeap[int]()
        heap.push(5)
        heap.push(3)
        print(heap.pop())  # 5
        
        # With key function
        heap = MaxHeap[str](key=len)  # Max by string length
        heap.push("a")
        heap.push("bbb")
        print(heap.pop())  # "bbb"
    """
    
    def __init__(self, key: Optional[Callable[[T], K]] = None):
        """
        Initialize a max-heap.
        
        Args:
            key: Optional function to extract comparison key from elements.
                 If None, elements are compared directly.
        """
        self._heap: List[HeapItem] = []
        self._key_func = key if key else lambda x: x
        self._counter = 0
    
    def push(self, value: T) -> None:
        """
        Insert an element into the heap.
        
        Time Complexity: O(log n)
        """
        key = self._key_func(value)
        # Negate key for max-heap behavior if numeric, else use wrapper
        if isinstance(key, (int, float)):
            negated_key = -key
        else:
            negated_key = _ReversedKey(key)
        
        item = HeapItem(key=negated_key, value=value, insertion_order=self._counter)
        heapq.heappush(self._heap, item)
        self._counter += 1
    
    def pop(self) -> T:
        """
        Remove and return the maximum element.
        
        Time Complexity: O(log n)
        Raises: IndexError if heap is empty
        """
        if not self._heap:
            raise IndexError("pop from empty heap")
        return heapq.heappop(self._heap).value
    
    def peek(self) -> T:
        """
        Return the maximum element without removing it.
        
        Time Complexity: O(1)
        Raises: IndexError if heap is empty
        """
        if not self._heap:
            raise IndexError("peek at empty heap")
        return self._heap[0].value
    
    def pushpop(self, value: T) -> T:
        """
        Push a new value, then pop and return the maximum.
        
        More efficient than separate push and pop.
        Time Complexity: O(log n)
        """
        if not self._heap:
            return value
        
        key = self._key_func(value)
        if isinstance(key, (int, float)):
            negated_key = -key
        else:
            negated_key = _ReversedKey(key)
        
        item = HeapItem(key=negated_key, value=value, insertion_order=self._counter)
        self._counter += 1
        
        # Compare with current max
        if item < self._heap[0]:
            return heapq.heapreplace(self._heap, item).value
        else:
            return value
    
    def __len__(self) -> int:
        return len(self._heap)
    
    def __bool__(self) -> bool:
        return bool(self._heap)
    
    def __repr__(self) -> str:
        values = [item.value for item in self._heap]
        return f"MaxHeap({values})"
 
 
class _ReversedKey:
    """Helper for reversing comparison of non-numeric keys."""
    __slots__ = ['value']
    
    def __init__(self, value):
        self.value = value
    
    def __lt__(self, other: '_ReversedKey') -> bool:
        return self.value > other.value
    
    def __eq__(self, other: '_ReversedKey') -> bool:
        return self.value == other.value
    
    def __ne__(self, other: '_ReversedKey') -> bool:
        return self.value != other.value
 
 
# ========== USAGE EXAMPLES ==========
 
def example_usage():
    # Numeric values
    int_heap = MaxHeap[int]()
    for val in [3, 1, 4, 1, 5, 9, 2, 6]:
        int_heap.push(val)
    
    while int_heap:
        print(int_heap.pop(), end=" ")  # 9 6 5 4 3 2 1 1
    print()
    
    # Strings by default (lexicographic)
    str_heap = MaxHeap[str]()
    for s in ["apple", "banana", "cherry"]:
        str_heap.push(s)
    
    print(str_heap.pop())  # "cherry"
    
    # Custom key function
    length_heap = MaxHeap[str](key=len)
    for s in ["a", "bbb", "cc"]:
        length_heap.push(s)
    
    print(length_heap.pop())  # "bbb" (length 3)