DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master heap sort completely — how heapify works, building a max-heap in O(n), the two-phase sorting process, why heap sort is O(n log n) in all cases with O(1) space, the weak cache performance trade-off, and comparison with merge sort and quick sort.
What Makes Heap Sort Special?
Heap sort combines the best properties of the two sorting extremes:
- Merge Sort: Guaranteed O(n log n) worst case
- Selection Sort: O(1) auxiliary space
Heap sort achieves both simultaneously. It is:
- Always O(n log n) — no bad input exists
- In-place — only O(1) extra memory
- Not stable — equal elements may change order
The Heapify Operation
heapify(arr, n, i) — restores the max-heap property for the subtree rooted at index i, assuming both children are already valid heaps.
Example
def heapify(arr, n, i):
"""
Restore max-heap property at index i.
n = current heap size.
Time: O(log n)
"""
largest = i # Assume root is largest
left = 2 * i + 1 # Left child
right = 2 * i + 2 # Right child
# If left child exists and is larger than root
if left < n and arr[left] > arr[largest]:
largest = left
# If right child exists and is larger than current largest
if right < n and arr[right] > arr[largest]:
largest = right
# If root is not the largest, swap and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest) # Recursively fix the affected subtree
Building a Max-Heap in O(n)
Starting from the last non-leaf node (index n//2 - 1) and going up to the root, call heapify on each node.
python example
def build_max_heap(arr):
"""
Build max-heap from unsorted array.
Time: O(n) — counterintuitively faster than O(n log n)
"""
n = len(arr)
# Start from last non-leaf, work toward root
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)Why O(n) and not O(n log n)?
At level h from bottom, nodes have subtrees of height h and require O(h) heapify work. There are ≤ n/2^(h+1) nodes at height h.
Total work = Σ (n/2^(h+1)) × O(h) for h=0 to log n = O(n × Σ h/2^h) = O(n × 2) = O(n) (geometric series: Σ h/2^h = 2)
The Complete Heap Sort Algorithm
Example
def heap_sort(arr):
"""
Phase 1: Build max-heap from array.
Phase 2: Repeatedly extract max, place at end.
Time: O(n log n) all cases. Space: O(1). Not stable.
"""
n = len(arr)
# Phase 1: Build max-heap — O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Phase 2: Extract max n-1 times — O(n log n)
for i in range(n - 1, 0, -1):
# Move current max (arr[0]) to end
arr[0], arr[i] = arr[i], arr[0]
# Restore heap property for reduced heap [0..i-1]
heapify(arr, i, 0)
return arr
print(heap_sort([12, 11, 13, 5, 6, 7])) # [5, 6, 7, 11, 12, 13]
Phase 2 trace:
| Max-heap | [13, 12, 7, 5, 6, 11] |
| Step 1: Swap arr[0]=13 with arr[5]=11 | [11,12,7,5,6,13] |
| Heapify [0..4] | [12,11,7,5,6] | 13 |
| Step 2: Swap arr[0]=12 with arr[4]=6 | [6,11,7,5,12] | 13 |
| Heapify [0..3] | [11,6,7,5] | 12,13 |
| Step 3: Swap arr[0]=11 with arr[3]=5 | [5,6,7,11] | 12,13 |
| Heapify [0..2] | [7,6,5] | 11,12,13 |
| Step 4: Swap arr[0]=7 with arr[2]=5 | [5,6,7] | 11,12,13 |
| Heapify [0..1] | [6,5] | 7,11,12,13 |
| Step 5: Swap arr[0]=6 with arr[1]=5 | [5,6] | 7,11,12,13 |
| Final | [5, 6, 7, 11, 12, 13] ✓ |
Complexity Analysis
Time — O(n log n) All Cases
- Phase 1 (build heap): O(n)
- Phase 2 (n-1 extractions × O(log n) heapify each): O(n log n)
- Total: O(n + n log n) = O(n log n)
Critical property: No bad input exists. Heapify always takes O(log n). Unlike Quick Sort, there is no degenerate case.
Space — O(1)
Everything happens in-place within the original array. The heap structure is implicit in the array indices — no separate heap data structure is allocated.
The recursive heapify uses O(log n) call stack, but this can be converted to an iterative loop:
Example
def heapify_iterative(arr, n, i):
"""Iterative heapify — O(1) extra space."""
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 # Heap property restored
arr[i], arr[largest] = arr[largest], arr[i]
i = largest # Continue down
Why Heap Sort is Not Used in Practice
Despite its impressive theoretical properties, Heap Sort is rarely used in practice:
Poor Cache Performance
Heap operations access memory in a non-sequential pattern
heapify at root (index 0) accesses:
index 0 → children at 1, 2
index 1 → children at 3, 4
index 3 → children at 7, 8
...
These jump around in memory → cache misses on every access
Compare with Quick Sort
Partition: sequential scan from left and right → cache hits
For large arrays on modern hardware, Heap Sort is 2-5x slower than Quick Sort despite the same O(n log n) asymptotic complexity.
Unstable
Heap Sort does not preserve the relative order of equal elements.
Comparison of O(n log n) Sorts
| Property | Merge Sort | Quick Sort | Heap Sort |
|---|---|---|---|
| Worst case | O(n log n) ✅ | O(n²) ❌ | O(n log n) ✅ |
| Average case | O(n log n) | O(n log n) | O(n log n) |
| Space | O(n) ❌ | O(log n) | O(1) ✅ |
| Stable | ✅ Yes | ❌ No | ❌ No |
| Cache friendly | Medium | ✅ Yes | ❌ Poor |
| Adaptive | ❌ No | ❌ No | ❌ No |
| Practical speed | Good | Best | Worst |
Heap Sort's niche: When both O(n log n) guarantee AND O(1) space are simultaneously required — a rare but real constraint in embedded systems and real-time applications.
Summary
Heap sort: build a max-heap, then repeatedly extract the maximum.
- Always O(n log n) — no bad input
- O(1) space — completely in-place
- Not stable — equal elements may reorder
- Poor cache performance — non-sequential memory access
- Best used when: Both worst-case guarantee AND minimal memory are required simultaneously
*Next Lesson: Counting Sort*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap Sort — Guaranteed O(n log n) with O(1) Space.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, sorting, heap, sort
Related Data Structures & Algorithms Topics
Continue learning this concept
SortingBubble Sort — Complete Analysis with Optimizations and When to Use ItMaster bubble sort completely — the mechanism, step-by-step trace, optimized version with early termination, formal proof of correctness, time and space complexity analysis with all three cases, comparison with other O(n²) sorts, and when bubble sort is actually useful.SortingCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundMaster counting sort — how it breaks the O(n log n) comparison lower bound, the complete O(n+k) algorithm with stability proof, when k must be small for counting sort to be practical, the cumulative count technique for stable output, and applications in radix sort and frequency counting.SortingInsertion Sort — The O(n) Best Case Sort That Powers PythonMaster insertion sort completely — the card-dealing analogy, step-by-step trace, O(n) best case proof, binary insertion sort optimization, why it is used in PythonSortingMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortMaster merge sort completely — the divide-and-conquer approach, step-by-step trace, formal correctness proof, recurrence relation solution, bottom-up vs top-down implementation, natural merge sort for nearly sorted data, counting inversions, and all comparison-based optimizations.SortingQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisMaster quick sort completely — partition schemes (Lomuto and Hoare), randomized quick sort, 3-way partition for duplicates, average-case proof, worst-case prevention, why quick sort beats merge sort in practice despite equal asymptotic complexity, and tail-call optimization.SortingRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesMaster radix sort — LSD and MSD variants, how it uses counting sort as a subroutine to sort digit by digit, why it achieves O(nk) time, sorting strings and multi-field records, comparison with counting sort and comparison sorts, and practical applications.