7a:T501,Before we can understand heap sort, we need a crystal-clear understanding of what a heap actually is. A **heap** is a complete binary tree that satisfies the **heap property**. Let's dissect these two components with the precision they deserve. **Complete Binary Tree:** A complete binary tree is a binary tree where every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. This structural constraint is crucial because it allows us to represent the tree efficiently in an array without any wasted space or pointers. For a node at index `i` (using 0-based indexing): - Left child is at index `2i + 1` - Right child is at index `2i + 2` - Parent is at index `⌊(i - 1) / 2⌋` **The Heap Property:** The heap property comes in two flavors: - **Max-Heap Property:** Every node's value is greater than or equal to the values of its children. The maximum element is always at the root. - **Min-Heap Property:** Every node's value is less than or equal to the values of its children. The minimum element is always at the root. For sorting in ascending order, we use a max-heap. The key insight is that the max-heap property gives us instant access to the largest element—it's always sitting at the root, index 0.7b:T439,def heap_sort_concept(arr): """ Conceptual demonstration of heap sort's core logic. The algorithm has two phases: 1. Build a max-heap from the array 2. Repeatedly extract the maximum and place it at the end """ n = len(arr) # Phase 1: Build max-heap # After this, arr[0] is guaranteed to be the maximum build_max_heap(arr) # Phase 2: Extract maximums one by one for i in range(n - 1, 0, -1): # The maximum element is at arr[0] # Swap it with the last element of the current heap arr[0], arr[i] = arr[i], arr[0] # Now arr[i] through arr[n-1] are sorted # The heap is now arr[0] through arr[i-1] # But the heap property may be violated at the root # Restore heap property for the reduced heap # The heap now has size i (indices 0 to i-1) heapify_down(arr, 0, i) # The array is now sorted in ascending order return arr # Note: This is conceptual pseudocode # Full implementation with heapify shown in subsequent pages7c:T487,function heapSortConcept(arr: number[]): number[] { /** * Conceptual demonstration of heap sort's core logic. * * The algorithm has two phases: * 1. Build a max-heap from the array * 2. Repeatedly extract the maximum and place it at the end */ const n = arr.length; // Phase 1: Build max-heap // After this, arr[0] is guaranteed to be the maximum buildMaxHeap(arr); // Phase 2: Extract maximums one by one for (let i = n - 1; i > 0; i--) { // The maximum element is at arr[0] // Swap it with the last element of the current heap [arr[0], arr[i]] = [arr[i], arr[0]]; // Now arr[i] through arr[n-1] are sorted // The heap is now arr[0] through arr[i-1] // But the heap property may be violated at the root // Restore heap property for the reduced heap // The heap now has size i (indices 0 to i-1) heapifyDown(arr, 0, i); } // The array is now sorted in ascending order return arr; } // Note: This is conceptual pseudocode // Full implementation with heapify shown in subsequent pages7d:T549,To appreciate heap sort's elegance, we need to understand why the heap structure is so naturally suited for sorting. The answer lies in the mathematical properties of the heap. **Property 1: Partial Ordering** A heap doesn't maintain a total ordering—elements aren't sorted. Instead, it maintains a *partial ordering*: every node is larger than its descendants. This weaker constraint is both the source of the heap's efficiency and its limitation. - Finding the maximum: O(1) — It's always at the root. - Finding the kth largest: O(k log n) — We must extract k times. - Finding an arbitrary element: O(n) — No efficient search path. For sorting, we only care about repeatedly finding maximums, which is exactly what heaps do efficiently. **Property 2: Logarithmic Height** A complete binary tree with n nodes has height ⌊log₂ n⌋. This means: - Heapify operations traverse at most log n levels. - Both bubble-up and bubble-down are O(log n). - The tree structure provides the halving behavior essential for efficient algorithms. **Property 3: Array Representation** The complete binary tree structure allows pointer-free array storage: - No memory overhead for left/right pointers. - Cache-friendly sequential access patterns. - O(1) parent and child index calculations. - The same array stores both the heap and the sorted result.7e:T439,**Why Heap Sort Is Often Slower in Practice:** Despite having the same O(n log n) complexity, heap sort typically runs slower than quick sort by a constant factor of 2-3x. The reasons are instructive: 1. **Poor Cache Locality:** Heap operations jump between non-contiguous memory locations. When heapifying, we compare parent with children at indices that may be far apart in memory. This causes frequent cache misses. 2. **More Comparisons:** Heap sort performs more comparisons than quick sort on average. Each heapify operation must check both children, and the extraction phase doesn't benefit from early termination. 3. **Branch Prediction:** The comparison patterns in heap sort are less predictable than in quick sort, leading to more branch mispredictions. 4. **Constant Factors:** The index arithmetic for parent/child calculations adds overhead that doesn't exist in simpler algorithms. This illustrates a crucial principle: **asymptotic complexity isn't the whole story**. Real performance depends on constant factors, cache behavior, and hardware characteristics.7f:T4f0,Understanding heap sort deeply requires understanding the mathematics of heaps. Let's examine the key mathematical properties that make heap sort work. **Heap Height Analysis:** For a heap with n elements: - Height h = ⌊log₂ n⌋ - Nodes at level k (0-indexed from root): min(2^k, n - 2^k + 1) - Leaves are at levels h or h-1 only - At least n/2 nodes are leaves (cannot have children) The last point is crucial: **more than half the nodes in a heap are leaves**. This affects both build heap efficiency and heapify cost distribution. **The Heapify Invariant:** The heapify (or sift-down) operation maintains the following invariant: > If both children of node i are roots of valid heaps, after heapify(i), the subtree rooted at i is a valid heap. This invariant is the foundation of both building a heap and extracting elements. We can build bottom-up because leaves are trivially valid heaps. **Counting Comparisons:** For extracting all elements: - First extraction: heapify from root, at most 2h comparisons - Each subsequent: heapify on a shrinking heap - Total: roughly 2n log n comparisons in the worst case For building the heap (analyzed in the next page): - Not O(n log n), but O(n) - The proof involves summing contributions from each level80:T7dc,def analyze_heap_properties(n: int) -> dict: """ Analyze mathematical properties of a heap with n elements. This demonstrates the mathematical relationships that underpin heap sort's efficiency guarantees. """ import math if n <= 0: return {"error": "n must be positive"} # Height of the heap (0-indexed) height = math.floor(math.log2(n)) if n > 0 else 0 # Number of nodes at each level nodes_per_level = [] remaining = n for level in range(height + 1): max_at_level = 2 ** level actual = min(max_at_level, remaining) nodes_per_level.append(actual) remaining -= actual # Number of leaves (nodes without children) # A node at index i has children at 2i+1 and 2i+2 # So node i is a leaf iff 2i+1 >= n, i.e., i >= (n-1)/2 num_leaves = n - (n // 2) # Equivalent: ceiling(n/2) num_internal = n // 2 # Maximum comparisons for heapify from root # At each level, we compare with up to 2 children max_heapify_comparisons = 2 * height # Worst-case comparisons for heap sort (rough upper bound) # Build heap: O(n) comparisons # Extract phase: O(n log n) comparisons extraction_comparisons_upper = 2 * n * height return { "n": n, "height": height, "nodes_per_level": nodes_per_level, "num_leaves": num_leaves, "num_internal_nodes": num_internal, "leaf_fraction": num_leaves / n, "max_heapify_comparisons": max_heapify_comparisons, "extraction_phase_upper_bound": extraction_comparisons_upper, } # Example analysis if __name__ == "__main__": for size in [7, 15, 31, 1000, 1000000]: props = analyze_heap_properties(size) print(f" Heap with {size} elements:") print(f" Height: {props['height']}") print(f" Leaves: {props['num_leaves']} ({props['leaf_fraction']:.1%})") print(f" Internal nodes: {props['num_internal_nodes']}")81:T424,The entire heap sort algorithm rests on a single fundamental operation: **heapify** (also called "sift-down" or "percolate-down"). This operation restores the heap property when it's violated at a single node, assuming its children's subtrees are already valid heaps. **The Heapify Algorithm:** 1. Start at node i (where the violation might exist) 2. Compare node i with its children 3. If node i is smaller than its largest child, swap them 4. Repeat from the position where the original node ended up 5. Stop when the node is larger than both children OR when it becomes a leaf The key insight is that swapping with the **larger** child maintains the heap property in the other subtree. If we swapped with the smaller child, the new parent would be smaller than the other child, violating the heap property. **Why Heapify Is O(log n):** Each iteration moves down one level in the tree. Since the tree has height log n, we perform at most log n iterations. Each iteration does O(1) work (comparisons and a potential swap). Therefore, heapify is O(log n).82:T8e9,def heapify(arr: list, n: int, i: int) -> None: """ Restore the max-heap property for the subtree rooted at index i. Preconditions: - The left and right subtrees of node i are valid max-heaps - n is the size of the heap (indices 0 to n-1) - i is a valid index in the heap (0 <= i < n) Postcondition: - The subtree rooted at i is a valid max-heap Time Complexity: O(log n) - at most h iterations where h is height Space Complexity: O(1) - iterative, no auxiliary storage """ while True: largest = i # Assume root of this subtree is largest left = 2 * i + 1 # Left child index right = 2 * i + 2 # Right child index # Check if left child exists and is larger than current largest if left < n and arr[left] > arr[largest]: largest = left # Check if right child exists and is larger than current largest if right < n and arr[right] > arr[largest]: largest = right # If largest is still i, heap property is satisfied if largest == i: break # We're done # Swap the current node with the largest child arr[i], arr[largest] = arr[largest], arr[i] # Continue heapifying from the position we swapped to # The violation has "moved down" to the child's position i = largest def heapify_recursive(arr: list, n: int, i: int) -> None: """ Recursive version of heapify for conceptual clarity. Same behavior as iterative version, but uses recursion to express the "bubble down" nature more explicitly. Time Complexity: O(log n) Space Complexity: O(log n) due to recursion stack """ largest = i left = 2 * i + 1 right = 2 * i + 2 # Find the largest among root, left child, right child if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right # If root is not largest, swap and continue heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # Recursively heapify the affected subtree heapify_recursive(arr, n, largest)83:T7f3,function heapify(arr: number[], n: number, i: number): void { /** * Restore the max-heap property for the subtree rooted at index i. * * Preconditions: * - The left and right subtrees of node i are valid max-heaps * - n is the size of the heap (indices 0 to n-1) * - i is a valid index in the heap (0 <= i < n) * * Postcondition: * - The subtree rooted at i is a valid max-heap * * Time Complexity: O(log n) - at most h iterations where h is height * Space Complexity: O(1) - iterative, no auxiliary storage */ while (true) { let largest = i; // Assume root of this subtree is largest const left = 2 * i + 1; // Left child index const right = 2 * i + 2; // Right child index // Check if left child exists and is larger than current largest if (left < n && arr[left] > arr[largest]) { largest = left; } // Check if right child exists and is larger than current largest if (right < n && arr[right] > arr[largest]) { largest = right; } // If largest is still i, heap property is satisfied if (largest === i) { break; // We're done } // Swap the current node with the largest child [arr[i], arr[largest]] = [arr[largest], arr[i]]; // Continue heapifying from the position we swapped to i = largest; } } function heapifyRecursive(arr: number[], n: number, i: number): void { /** * Recursive version of heapify for conceptual clarity. */ let largest = i; const left = 2 * i + 1; const right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest !== i) { [arr[i], arr[largest]] = [arr[largest], arr[i]]; heapifyRecursive(arr, n, largest); } }72:{"json":{"id":"seed_5ed1b9a15a523de18ecf2368cdad5f6e","slug":"heap-sort","category":"Data Structures & Algorithms","topic":"Sorting Algorithms","title":"Heap Sort — Heap-Based Sorting","description":"Master heap sort, a powerful sorting algorithm that leverages the heap data structure to achieve guaranteed O(n log n) time complexity. Learn how heaps enable efficient sorting, understand the build heap and extract max operations, and discover how to implement heap sort in-place with O(1) extra space.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_93164d136dc2b75c32b64da19cab8988","title":"Using a Heap for Sorting","order":0,"content":[{"id":"opening-hook","title":"When Data Structures Become Algorithms","content":[{"data":{"content":"In the world of algorithms, certain data structures are so intimately connected to specific computational problems that the structure itself *becomes* the algorithm. The heap is perhaps the most profound example of this phenomenon. When you truly understand what a heap is and what invariants it maintains, the heap sort algorithm doesn't require memorization—it emerges naturally as an inevitable consequence of the structure's properties.\n\nHeap sort occupies a unique and fascinating position in the sorting algorithm landscape. It combines the guaranteed O(n log n) worst-case performance of merge sort with the in-place nature of quick sort, all while being built on one of the most elegant data structures in computer science. Understanding heap sort isn't just about learning another sorting algorithm—it's about seeing how a well-designed data structure can solve problems through its very existence."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand why heaps are natural sorting machines, how the heap property directly enables efficient sorting, and why heap sort guarantees O(n log n) performance even in worst-case scenarios. You'll see how the mathematical structure of heaps makes them ideal for extracting elements in sorted order.","variant":"info"},"type":"callout"}]},{"id":"heap-revisited","title":"The Heap Data Structure Revisited","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"rows":[["Find Maximum","O(1)","Maximum is always at the root (index 0)"],["Extract Maximum","O(log n)","Remove root, replace with last element, heapify down"],["Insert","O(log n)","Add at end, heapify up to maintain property"],["Heapify (single node)","O(log n)","Restore heap property for a subtree"],["Build Heap","O(n)","Convert arbitrary array to valid heap"],["Heap Sort","O(n log n)","Build heap + n extract operations"]],"caption":"Heap Operations and Their Complexities","headers":["Operation","Time Complexity","Description"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Array Representation Insight","content":"The fact that a complete binary tree can be stored in an array with O(1) parent/child access is not just convenient—it's the reason heap sort can be implemented in-place. We're not juggling pointers or allocating tree nodes; we're simply treating an array as if it were a tree. This representation is the foundation of heap sort's space efficiency.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"heap-to-sorted","title":"From Heap to Sorted Array: The Core Insight","content":[{"data":{"content":"Here's the fundamental insight that makes heap sort possible: **a max-heap always tells you the largest element in constant time**. If you repeatedly extract the maximum element and place it at the end of the array, you end up with a sorted array.\n\nLet's trace through this logic step by step:\n\n**Step 1:** Start with a max-heap. The largest element is at position 0.\n\n**Step 2:** Swap the root (largest element) with the last element in the heap.\n\n**Step 3:** The largest element is now in its final sorted position. Reduce the heap size by 1 (conceptually removing it from the heap).\n\n**Step 4:** The new root probably violates the heap property. Restore it by \"heapifying down\" from the root.\n\n**Step 5:** Repeat steps 2-4 until the heap size is 1.\n\nWhat remains is a sorted array, achieved without any additional space allocation. The elements that were \"removed\" from the heap are actually just sitting at the end of the same array, accumulating in sorted order."},"type":"text"},{"data":{"fileName":"heap_sort_concept.py","languages":[{"code":"$7b","label":"Python","value":"python"},{"code":"$7c","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Why This Works:**\n\nThe brilliance of heap sort lies in its invariant maintenance. After each extraction:\n\n1. **The sorted portion grows:** Each extracted maximum goes to its correct final position.\n2. **The heap portion shrinks:** We conceptually reduce the heap by one element.\n3. **The heap property is restored:** A single heapify operation fixes any violation.\n\nThe cost per extraction is O(log n) for the heapify operation. With n - 1 extractions, the total is O(n log n) for the extraction phase. Combined with O(n) for building the heap (which we'll examine closely), the overall complexity is O(n log n)."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"why-heaps-enable","title":"Why Heaps Enable Efficient Sorting","content":[{"data":{"content":"$7d"},"type":"text"},{"data":{"left":[{"data":{"items":["**O(1) maximum access** — Root is always the largest","**O(log n) extraction** — Heapify restores property quickly","**O(n) construction** — Build heap is surprisingly efficient","**In-place storage** — No auxiliary data structures","**Deterministic performance** — No bad input orderings"],"title":{"icon":"CheckCircle","text":"What Heaps Give Us","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Efficient search** — O(n) to find arbitrary elements","**Total ordering** — Only partial order maintained","**Stability** — Equal elements may be reordered","**Cache optimization** — Less cache-friendly than sequential access","**Adaptive behavior** — No speedup for nearly-sorted input"],"title":{"icon":"XCircle","text":"What Heaps Don't Give Us","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Info","title":"The Sorting Machine Metaphor","content":"Think of a max-heap as a specialized machine that always has the largest unsorted element ready for output. Each time we take an element from the machine (extract max), it internally reorganizes to present the next largest. Heap sort is simply running this machine n times and collecting the output in reverse order.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"heapsort-comparison","title":"Heap Sort in the Sorting Algorithm Landscape","content":[{"data":{"content":"Heap sort occupies a unique position among sorting algorithms. To understand its role, let's compare it to the other major O(n log n) sorts: merge sort and quick sort.\n\n**The Three-Way Comparison:**\n\nEach of these algorithms makes different tradeoffs:\n\n- **Merge Sort:** Guarantees O(n log n) always, but requires O(n) extra space. Stable.\n- **Quick Sort:** O(n log n) expected, but O(n²) worst case. In-place (O(log n) stack). Not stable.\n- **Heap Sort:** Guarantees O(n log n) always AND is in-place. Not stable.\n\nHeap sort is the only algorithm that achieves both guaranteed O(n log n) time and O(1) extra space. This makes it theoretically optimal in both dimensions, yet in practice, it's often the slowest of the three. Understanding why reveals important lessons about algorithm analysis."},"type":"text"},{"data":{"rows":[["Best Case Time","O(n log n)","O(n log n)","O(n log n)"],["Average Case Time","O(n log n)","O(n log n)","O(n log n)"],["Worst Case Time","O(n log n)","O(n²)","O(n log n)"],["Space Complexity","O(n)","O(log n) stack","O(1)"],["Stable","Yes","No (typically)","No"],["Adaptive","No","No (standard)","No"],["Cache Performance","Good (sequential)","Excellent","Poor (scattered)"],["In-Place","No","Yes","Yes"]],"caption":"Detailed Comparison of O(n log n) Sorting Algorithms","headers":["Property","Merge Sort","Quick Sort","Heap Sort"]},"type":"table"},{"data":{"content":"$7e"},"type":"text"},{"data":{"icon":"Lightbulb","title":"When Heap Sort Shines","content":"Heap sort is ideal when you need guaranteed worst-case performance (quick sort's O(n²) is unacceptable), cannot afford extra memory (merge sort's O(n) is too much), or are implementing systems where predictable timing matters more than average-case speed—like real-time systems or security-critical applications where timing attacks are a concern.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"mathematical-foundation","title":"The Mathematical Foundation","content":[{"data":{"content":"$7f"},"type":"text"},{"data":{"fileName":"heap_math_properties.py","languages":[{"code":"$80","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"The Power of Binary Structure","content":"The heap's logarithmic height is a direct consequence of the binary tree structure. Each level doubles the capacity. This is the same halving principle that makes binary search efficient, and it appears throughout computer science. When you see 'log n' in a complexity, there's usually a halving or doubling pattern at work.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"understanding-heapify","title":"Understanding Heapify: The Core Operation","content":[{"data":{"content":"$81"},"type":"text"},{"data":{"fileName":"heapify_operation.py","languages":[{"code":"$82","label":"Python","value":"python"},{"code":"$83","label":"TypeScript","value":"typescript"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Critical Implementation Detail","content":"When comparing children, we must use the **larger** child for swapping in a max-heap. Swapping with the smaller child would leave the other child larger than the new parent, immediately violating the heap property. This choice isn't arbitrary—it's essential for correctness.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"visualizing-process","title":"Visualizing the Heap Sort Process","content":[{"data":{"content":"To truly understand heap sort, let's trace through a complete example. We'll sort the array `[4, 10, 3, 5, 1, 8, 7]`.\n\n**Phase 1: Build the Heap**\n\nStarting array (viewed as complete binary tree):\n```\n 4\n / \n 10 3\n / \\ / \n 5 1 8 7\n```\n\nHeapifying from the last non-leaf node (index 2) upward:\n\n1. Heapify at index 2 (value 3): 8 > 3, swap → 3 and 8 swap\n2. Heapify at index 1 (value 10): 10 > 5 and 10 > 1, no swap needed\n3. Heapify at index 0 (value 4): 10 > 4, swap → 4 moves down, continue heapifying\n\nAfter build heap, we have a valid max-heap with 10 at the root."},"type":"text"},{"data":{"rows":[["Initial","Input array","[4, 10, 3, 5, 1, 8, 7]","None"],["Build 1","Heapify index 2","[4, 10, 8, 5, 1, 3, 7]","None"],["Build 2","Heapify index 1 (no change)","[4, 10, 8, 5, 1, 3, 7]","None"],["Build 3","Heapify index 0","[10, 5, 8, 4, 1, 3, 7]","None"],["Extract 1","Swap root with last, heapify","[8, 5, 7, 4, 1, 3 | 10]","[10]"],["Extract 2","Swap root with last, heapify","[7, 5, 3, 4, 1 | 8, 10]","[8, 10]"],["Extract 3","Swap root with last, heapify","[5, 4, 3, 1 | 7, 8, 10]","[7, 8, 10]"],["Extract 4","Swap root with last, heapify","[4, 1, 3 | 5, 7, 8, 10]","[5, 7, 8, 10]"],["Extract 5","Swap root with last, heapify","[3, 1 | 4, 5, 7, 8, 10]","[4, 5, 7, 8, 10]"],["Extract 6","Swap root with last","[1 | 3, 4, 5, 7, 8, 10]","[3, 4, 5, 7, 8, 10]"],["Final","Heap size = 1, done","[1, 3, 4, 5, 7, 8, 10]","Sorted!"]],"caption":"Trace of Heap Sort on [4, 10, 3, 5, 1, 8, 7]","headers":["Step","Action","Array State","Sorted Portion"]},"type":"table"},{"data":{"content":"**Key Observations:**\n\n1. **The heap shrinks from the right:** Each extraction reduces the heap portion while growing the sorted portion at the end.\n\n2. **Maximum travels to the end:** Each step places the current maximum in its final sorted position.\n\n3. **In-place transformation:** The same array holds both the shrinking heap and the growing sorted section.\n\n4. **Consistent work per extraction:** Each extraction does O(log n) work regardless of the values involved.\n\nThis visualization helps cement the intuition: we're essentially running a selection sort, but instead of O(n) to find each maximum, the heap gives us O(1) access (and O(log n) to restore the property)."},"type":"text"},{"data":{"icon":"CheckCircle","title":"The Invariant Perspective","content":"At any point during extraction: the first k positions form a valid max-heap, and the last (n-k) positions contain the (n-k) largest elements in sorted order. When k=1, everything after index 0 is sorted, and index 0 is trivially sorted with itself.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Why Use a Heap for Sorting","content":[{"data":{"content":"We've established the conceptual foundation of heap sort. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Heaps provide O(1) maximum access** — The heap property ensures the largest element is always at the root, enabling efficient repeated extraction.","**Heapify is the core operation** — The O(log n) heapify operation restores the heap property after extraction, making each 'find max' essentially O(log n) amortized.","**Array representation enables in-place sorting** — The complete binary tree structure fits perfectly in an array, allowing heap sort to use only O(1) extra space.","**Guaranteed worst-case performance** — Unlike quick sort, heap sort achieves O(n log n) even in the worst case, with no bad input patterns.","**The tradeoff is cache performance** — Heap operations access scattered memory locations, making heap sort slower in practice than quick sort despite matching asymptotic bounds.","**Heap sort emerges from heap structure** — Understanding heaps deeply means the sorting algorithm follows naturally rather than requiring memorization."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Looking Ahead:**\n\nIn the next page, we'll dive deep into the two-phase structure of heap sort: building the initial heap and repeatedly extracting the maximum. We'll analyze the surprisingly efficient O(n) build-heap algorithm and understand exactly how the extraction phase achieves sorting. You'll see the complete, production-ready implementation and understand every line."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand why heaps are natural sorting machines. The heap data structure, with its O(1) maximum access and O(log n) restoration, provides exactly the operations needed for efficient sorting. Next, we'll examine the build heap operation and extraction phase in complete detail.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_12e57fdb2d5d8f54320d1ab1b7fb4141","title":"Build Heap, Repeatedly Extract Max","order":1,"content":null,"isLocked":true},{"id":"seed_fbe29921b3003d91e76393d4cc03f51e","title":"Time Complexity: O(n log n) Guaranteed","order":2,"content":null,"isLocked":true},{"id":"seed_3b1a9a5e95dd8000314be32def3456ee","title":"In-Place Sorting with Heaps","order":3,"content":null,"isLocked":true}]}}