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

"""
Visualizing how an array represents a complete binary tree
and how this enables in-place heap sort.
"""
 
 
def visualize_heap_array(arr: list) -> str:
    """
    Create ASCII visualization of array as complete binary tree.
    
    Shows how the same array can be viewed as both:
    1. A plain array (for sorting)
    2. A heap structure (during algorithm execution)
    """
    if not arr:
        return "Empty heap"
    
    n = len(arr)
    lines = []
    
    # Calculate tree height
    height = 0
    temp = n
    while temp > 0:
        height += 1
        temp = (temp - 1) // 2 if temp > 1 else 0
    
    # Create level-by-level visualization
    level_start = 0
    level_size = 1
    max_width = 2 ** height * 4  # Approximate width
    
    while level_start < n:
        level_end = min(level_start + level_size, n)
        values = arr[level_start:level_end]
        
        # Calculate spacing
        nodes_in_level = len(values)
        spacing = max_width // (nodes_in_level + 1)
        
        # Build level string
        level_str = ""
        for i, val in enumerate(values):
            pos = spacing * (i + 1)
            level_str += " " * (pos - len(level_str)) + str(val)
        
        lines.append(level_str)
        
        level_start = level_end
        level_size *= 2
    
    return "\n".join(lines)
 
 
def show_array_to_tree_mapping(arr: list) -> None:
    """
    Show the explicit mapping between array indices and tree positions.
    """
    n = len(arr)
    
    print("Array representation:")
    print(f"  Indices: {list(range(n))}")
    print(f"  Values:  {arr}")
    print()
    
    print("Tree relationships (0-indexed):")
    for i in range(n):
        left = 2 * i + 1
        right = 2 * i + 2
        parent = (i - 1) // 2 if i > 0 else None
        
        parts = [f"Index {i} (value {arr[i]}):"]
        if parent is not None:
            parts.append(f"parent={parent}")
        if left < n:
            parts.append(f"left={left}")
        if right < n:
            parts.append(f"right={right}")
        if left >= n:
            parts.append("(leaf)")
        
        print("  " + " ".join(parts))
 
 
def demonstrate_in_place_transformation():
    """
    Demonstrate how the same array transitions during heap sort.
    """
    print("=" * 60)
    print("In-Place Transformation During Heap Sort")
    print("=" * 60)
    
    arr = [4, 10, 3, 5, 1, 8, 7]
    n = len(arr)
    
    print(f"\nInitial array: {arr}")
    print("Viewed as complete binary tree:")
    print()
    show_array_to_tree_mapping(arr)
    
    # After build heap
    def heapify(arr, heap_size, i):
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < heap_size and arr[left] > arr[largest]:
                largest = left
            if right < heap_size and arr[right] > arr[largest]:
                largest = right
            if largest == i:
                break
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest
    
    print("\n" + "-" * 60)
    print("After BUILD-HEAP:")
    
    for i in range((n // 2) - 1, -1, -1):
        heapify(arr, n, i)
    
    print(f"Array: {arr}")
    print("Interpretation: [entire array is max-heap]")
    
    # After first extraction
    print("\n" + "-" * 60)
    print("After FIRST EXTRACTION (swap root with last, heapify):")
    
    arr[0], arr[n-1] = arr[n-1], arr[0]
    heapify(arr, n-1, 0)
    
    print(f"Array: {arr}")
    print(f"Interpretation: [{arr[:n-1]}] is heap, [{arr[n-1:]}] is sorted")
    
    # Continue showing the transformation
    heap_size = n - 1
    while heap_size > 1:
        arr[0], arr[heap_size-1] = arr[heap_size-1], arr[0]
        heap_size -= 1
        heapify(arr, heap_size, 0)
    
    print("\n" + "-" * 60)
    print("FINAL STATE:")
    print(f"Array: {arr}")
    print("Interpretation: entire array is sorted!")
    print("\nKey insight: Same memory, different interpretations at each stage.")
 
 
if __name__ == "__main__":
    demonstrate_in_place_transformation()

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

"""
Detailed demonstration of the shrinking heap / growing sorted mechanism.
"""
 
 
def heap_sort_with_visualization(arr: list) -> list:
    """
    Heap sort with step-by-step visualization of the two-section invariant.
    """
    n = len(arr)
    steps = []
    
    def heapify(arr, heap_size, i):
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < heap_size and arr[left] > arr[largest]:
                largest = left
            if right < heap_size and arr[right] > arr[largest]:
                largest = right
            
            if largest == i:
                break
            
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest
    
    # Build max-heap
    for i in range((n // 2) - 1, -1, -1):
        heapify(arr, n, i)
    
    steps.append({
        "phase": "Build Complete",
        "heap_size": n,
        "heap": arr.copy(),
        "sorted": [],
        "array": arr.copy()
    })
    
    # Extraction phase
    for heap_size in range(n, 1, -1):
        # Record before swap
        max_element = arr[0]
        
        # Swap max to sorted section
        arr[0], arr[heap_size - 1] = arr[heap_size - 1], arr[0]
        
        # Heapify reduced heap
        new_heap_size = heap_size - 1
        heapify(arr, new_heap_size, 0)
        
        steps.append({
            "phase": f"Extract {max_element}",
            "heap_size": new_heap_size,
            "heap": arr[:new_heap_size] if new_heap_size > 0 else [],
            "sorted": arr[new_heap_size:],
            "array": arr.copy()
        })
    
    return steps
 
 
def print_visualization(steps: list) -> None:
    """Print the step-by-step visualization."""
    print("=" * 70)
    print("Heap Sort: Shrinking Heap, Growing Sorted Section")
    print("=" * 70)
    
    for i, step in enumerate(steps):
        print(f"\nStep {i}: {step['phase']}")
        print(f"  Heap size: {step['heap_size']}")
        
        # Visual representation
        heap_part = step['heap']
        sorted_part = step['sorted']
        
        if heap_part and sorted_part:
            print(f"  Array: [{', '.join(map(str, heap_part))}  |  {', '.join(map(str, sorted_part))}]")
            print(f"          {'─' * (len(heap_part) * 3)}↑HEAP  " + 
                  f"{'─' * (len(sorted_part) * 3)}↑SORTED")
        elif sorted_part:
            print(f"  Array: [{', '.join(map(str, sorted_part))}]  ← ALL SORTED")
        else:
            print(f"  Array: [{', '.join(map(str, heap_part))}]  ← ALL HEAP")
        
        # Verify invariant
        if sorted_part:
            heap_max = max(heap_part) if heap_part else float('-inf')
            sorted_min = min(sorted_part)
            invariant_holds = heap_max <= sorted_min
            print(f"  Invariant (heap max ≤ sorted min): {invariant_holds} " +
                  f"({heap_max} ≤ {sorted_min})")
 
 
def demonstrate_space_usage():
    """Show that no extra space is used beyond a few variables."""
    print("\n" + "=" * 70)
    print("Space Usage Analysis")
    print("=" * 70)
    
    import sys
    
    arr = list(range(1000))
    
    # Space before sort
    print(f"\nArray of 1000 integers")
    print(f"Array size: {sys.getsizeof(arr)} bytes")
    
    print("\nVariables used during heap sort:")
    variables = [
        ("n (array length)", "int", 28),
        ("i (loop index)", "int", 28),
        ("heap_size (current size)", "int", 28),
        ("largest (comparison result)", "int", 28),
        ("left (child index)", "int", 28),
        ("right (child index)", "int", 28),
        ("temp (for swap)", "int", 28),
    ]
    
    total_aux = 0
    for name, type_, size in variables:
        print(f"  {name}: ~{size} bytes")
        total_aux += size
    
    print(f"\nTotal auxiliary space: ~{total_aux} bytes = O(1)")
    print("This is constant regardless of input size!")
    
    # Comparison with merge sort
    print("\nComparison with merge sort:")
    print(f"  Merge sort would need: ~{sys.getsizeof(arr)} extra bytes = O(n)")
    print(f"  Heap sort needs: ~{total_aux} bytes = O(1)")
 
 
if __name__ == "__main__":
    # Run visualization
    test_arr = [4, 10, 3, 5, 1, 8, 7]
    steps = heap_sort_with_visualization(test_arr.copy())
    print_visualization(steps)
    
    demonstrate_space_usage()

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

"""
Comparing recursive vs iterative heapify for space usage.
"""
import sys
 
 
def heapify_recursive(arr: list, n: int, i: int, depth: list = None) -> None:
    """
    Recursive heapify - O(log n) space due to call stack.
    
    The 'depth' parameter tracks recursion depth for demonstration.
    """
    if depth is not None:
        depth[0] = max(depth[0], len([f for f in iter(lambda: None, None)]))
    
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify_recursive(arr, n, largest, depth)  # Stack frame added
 
 
def heapify_iterative(arr: list, n: int, i: int) -> int:
    """
    Iterative heapify - O(1) space.
    
    Returns the number of iterations (levels traversed) for analysis.
    """
    iterations = 0
    
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest == i:
            break
        
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest
        iterations += 1
    
    return iterations
 
 
def measure_recursion_depth():
    """
    Measure the maximum recursion depth in recursive heapify.
    """
    import sys
    
    print("Measuring Recursion Depth in Recursive Heapify")
    print("=" * 50)
    
    # Create worst case: element at root must sink to bottom
    # This happens when building heap on reverse-sorted array
    
    for n in [100, 1000, 10000]:
        # Construct array where root sinks to leaf level
        arr = list(range(n, 0, -1))  # Reverse sorted
        
        # Manually track recursion
        frame_count = [0]
        
        def counting_heapify(arr, n, i):
            frame_count[0] += 1
            max_frame = frame_count[0]
            
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < n and arr[left] > arr[largest]:
                largest = left
            if right < n and arr[right] > arr[largest]:
                largest = right
            
            if largest != i:
                arr[i], arr[largest] = arr[largest], arr[i]
                counting_heapify(arr, n, largest)
            
            frame_count[0] -= 1
            return max_frame
        
        # Get max depth during build heap
        max_depth = 0
        old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(max(old_limit, n + 100))
        
        try:
            for i in range((n // 2) - 1, -1, -1):
                frame_count[0] = 0
                counting_heapify(arr, n, i)
                max_depth = max(max_depth, frame_count[0])
        except RecursionError:
            max_depth = "Stack Overflow!"
        
        sys.setrecursionlimit(old_limit)
        
        import math
        expected = math.floor(math.log2(n)) + 1
        print(f"n = {n:>6}: Max recursion depth = {max_depth}, expected log₂(n) = {expected}")
    
    print("\nConclusion: Recursion depth grows as O(log n)")
    print("For truly O(1) space, use iterative heapify.")
 
 
def demonstrate_iterative_advantage():
    """
    Show that iterative heapify uses constant space regardless of n.
    """
    print("\n" + "=" * 50)
    print("Iterative Heapify Space Usage")
    print("=" * 50)
    
    print("\nVariables used in iterative heapify:")
    print("  - i (current index)")
    print("  - largest (comparison result)")
    print("  - left (left child index)")
    print("  - right (right child index)")
    print("  Total: 4 integer variables = O(1)")
    
    print("\nSpace usage for various n:")
    for n in [100, 1000, 10000, 100000, 1000000]:
        # Iterative heapify always uses same variables
        space = 4 * 8  # 4 ints, ~8 bytes each on 64-bit
        print(f"  n = {n:>7}: {space} bytes (constant!)")
 
 
if __name__ == "__main__":
    measure_recursion_depth()
    demonstrate_iterative_advantage()

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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228

"""
Production-quality heap sort implementation.
 
Features:
- Strictly O(1) auxiliary space (iterative heapify)
- Handles edge cases (empty, single element, duplicates)
- Supports custom comparators for flexible ordering
- Type hints for clarity
- Comprehensive documentation
"""
from typing import TypeVar, Callable, List, Optional
 
T = TypeVar('T')
 
 
def heap_sort(
    arr: List[T],
    key: Optional[Callable[[T], any]] = None,
    reverse: bool = False
) -> None:
    """
    Sort a list in-place using heap sort.
    
    This implementation achieves:
    - Time Complexity: O(n log n) guaranteed (best, average, worst)
    - Space Complexity: O(1) auxiliary (strictly in-place)
    - Stability: Not stable (equal elements may be reordered)
    
    Args:
        arr: The list to sort. Modified in-place.
        key: Optional function to extract comparison key (like sorted()).
        reverse: If True, sort in descending order.
    
    Returns:
        None. The list is sorted in-place.
    
    Examples:
        >>> lst = [4, 2, 7, 1, 9]
        >>> heap_sort(lst)
        >>> lst
        [1, 2, 4, 7, 9]
        
        >>> lst = ["banana", "apple", "cherry"]
        >>> heap_sort(lst, key=len)
        >>> lst
        ['apple', 'banana', 'cherry']
    """
    n = len(arr)
    
    # Edge cases: empty or single element
    if n <= 1:
        return
    
    # Build comparison function
    compare = _build_comparator(key, reverse)
    
    # Phase 1: Build max-heap (O(n))
    _build_max_heap(arr, compare)
    
    # Phase 2: Extract maximum repeatedly (O(n log n))
    for heap_size in range(n, 1, -1):
        # Swap maximum (at root) with last heap element
        arr[0], arr[heap_size - 1] = arr[heap_size - 1], arr[0]
        
        # Restore heap property for reduced heap
        _heapify(arr, heap_size - 1, 0, compare)
 
 
def _build_comparator(
    key: Optional[Callable[[T], any]],
    reverse: bool
) -> Callable[[T, T], bool]:
    """
    Build a comparison function from key function and reverse flag.
    
    Returns a function compare(a, b) that returns True if a should be
    considered "greater than" b according to the heap ordering.
    """
    if key is None:
        if reverse:
            return lambda a, b: a < b  # Min-heap for descending sort
        else:
            return lambda a, b: a > b  # Max-heap for ascending sort
    else:
        if reverse:
            return lambda a, b: key(a) < key(b)
        else:
            return lambda a, b: key(a) > key(b)
 
 
def _build_max_heap(arr: List[T], compare: Callable[[T, T], bool]) -> None:
    """
    Transform array into a valid heap in-place.
    
    Works bottom-up, heapifying from the last non-leaf to the root.
    Time: O(n) — not O(n log n) despite calling O(n) heapify operations.
    """
    n = len(arr)
    last_non_leaf = (n // 2) - 1
    
    for i in range(last_non_leaf, -1, -1):
        _heapify(arr, n, i, compare)
 
 
def _heapify(
    arr: List[T],
    heap_size: int,
    i: int,
    compare: Callable[[T, T], bool]
) -> None:
    """
    Restore heap property for subtree rooted at index i.
    
    IMPORTANT: Uses iterative implementation for O(1) space.
    Recursive implementation would use O(log n) stack space.
    
    Precondition: Children subtrees are valid heaps.
    Postcondition: Subtree rooted at i is a valid heap.
    
    Args:
        arr: The array representing the heap
        heap_size: Current size of heap (indices 0 to heap_size-1)
        i: Index of node to heapify from
        compare: Comparison function, compare(a, b) returns True if a > b
    """
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        # Check if left child should be new root of this subtree
        if left < heap_size and compare(arr[left], arr[largest]):
            largest = left
        
        # Check if right child should be new root of this subtree
        if right < heap_size and compare(arr[right], arr[largest]):
            largest = right
        
        # If current node is already the largest, heap property satisfied
        if largest == i:
            return
        
        # Swap current with largest child and continue down
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest
 
 
# ============================================
# Convenience Functions
# ============================================
 
def heap_sorted(
    iterable,
    key: Optional[Callable[[T], any]] = None,
    reverse: bool = False
) -> List[T]:
    """
    Return a new sorted list from the items in iterable.
    
    Like built-in sorted(), but uses heap sort.
    Unlike sorted(), this is NOT stable.
    
    Args:
        iterable: Any iterable to sort
        key: Optional key function
        reverse: Sort descending if True
    
    Returns:
        New sorted list
    """
    result = list(iterable)
    heap_sort(result, key=key, reverse=reverse)
    return result
 
 
# ============================================
# Testing
# ============================================
 
def run_comprehensive_tests():
    """Run comprehensive test suite."""
    print("Heap Sort Production Implementation Tests")
    print("=" * 50)
    
    # Basic tests
    tests = [
        ([], []),
        ([1], [1]),
        ([2, 1], [1, 2]),
        ([3, 1, 2], [1, 2, 3]),
        ([4, 10, 3, 5, 1, 8, 7], [1, 3, 4, 5, 7, 8, 10]),
        ([1, 1, 1, 1], [1, 1, 1, 1]),
        ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
    ]
    
    passed = 0
    for input_arr, expected in tests:
        arr = input_arr.copy()
        heap_sort(arr)
        if arr == expected:
            passed += 1
            print(f"✓ {input_arr} → {arr}")
        else:
            print(f"✗ {input_arr} → {arr} (expected {expected})")
    
    print(f"\nBasic tests: {passed}/{len(tests)} passed")
    
    # Reverse sort test
    arr = [1, 5, 3, 2, 4]
    heap_sort(arr, reverse=True)
    print(f"\nReverse sort: {arr} (expected [5, 4, 3, 2, 1])")
    
    # Key function test
    words = ["banana", "apple", "cherry", "date"]
    heap_sort(words, key=len)
    print(f"Sort by length: {words}")
    
    # Large random test
    import random
    large = [random.randint(0, 100000) for _ in range(10000)]
    expected = sorted(large)
    heap_sort(large)
    large_correct = large == expected
    print(f"\nLarge random (10000 elements): {'✓' if large_correct else '✗'}")
 
 
if __name__ == "__main__":
    run_comprehensive_tests()