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 the min-heap data structure with complete from-scratch implementation — insert with sift-up, extract minimum with sift-down, decrease key, delete arbitrary element, build heap in O(n), and heap sort. All operations with detailed traces and complexity analysis.
The Min-Heap Property
In a min-heap, every parent node is ≤ its children. The minimum element is always at the root (index 0).
Example
Min-heap: 1
/ \
3 2
/ \ / \
9 7 4 8
Array: [1, 3, 2, 9, 7, 4, 8]
Operation Traces
Insert (Sift-Up)
| Append 2 to end | [1, 3, 4, 9, 7, 6, 8, 2] |
| i=7: parent=3, data[3]=9 > data[7]=2 | SWAP |
| i=3: parent=1, data[1]=3 > data[3]=2 | SWAP |
| i=1: parent=0, data[0]=1 ≤ data[1]=2 | STOP |
| Final | [1, 2, 4, 3, 7, 6, 8, 9] ✓ |
Extract Minimum (Sift-Down)
| Save root | min_val = 1 |
| Move last to root | [8, 3, 2, 9, 7, 4] |
| i=0 (value=8) | left=1(3), right=2(2) |
| smallest = 2 (right child, value=2) | SWAP |
| i=2 (value=8) | left=5(4), right=6(none) |
| smallest = 5 (left child, value=4) | SWAP |
| i=5 (value=8): left=11(none) | STOP |
| Final | [2, 3, 4, 9, 7, 8] ✓, return 1 |
Build Heap in O(n) — Why Not O(n log n)?
python example
# Naive approach: insert n elements one by one
# Each insert: O(log n) → Total: O(n log n)
# Heapify (build_heap): O(n)
def build_heap_efficient(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)Why O(n)? The mathematical analysis:
At height h from bottom:
- Nodes at height h: at most ⌈n/2^(h+1)⌉
- Work per node at height h: O(h) for sift-down
Total work = Σ h × n/2^(h+1) from h=0 to log n = n × Σ h/2^(h+1) = n × 1 (geometric series converges to 1) = O(n)
Heap Sort Using Min-Heap
Example
def heap_sort_ascending(arr):
"""Sort using min-heap: extract n minimums."""
heap = MinHeap(arr)
return [heap.pop() for _ in range(len(heap))]
print(heap_sort_ascending([3, 1, 4, 1, 5, 9, 2, 6]))
# [1, 1, 2, 3, 4, 5, 6, 9]
Merge K Sorted Arrays Using Min-Heap
Example
import heapq
def merge_k_sorted(arrays):
"""
Merge k sorted arrays into one sorted array.
Use min-heap to always get the global minimum.
Time: O(n log k) where n = total elements, k = number of arrays.
"""
result = []
# Heap: (value, array_index, element_index)
heap = []
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
next_idx = elem_idx + 1
if next_idx < len(arrays[arr_idx]):
heapq.heappush(heap, (arrays[arr_idx][next_idx], arr_idx, next_idx))
return result
print(merge_k_sorted([[1,4,7],[2,5,8],[3,6,9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
Operations Complexity
| Operation | Time | Notes |
|---|---|---|
push(value) | O(log n) | Sift up from leaf |
pop() | O(log n) | Sift down from root |
peek() | O(1) | Direct root access |
decrease_key(i, v) | O(log n) | Sift up from index i |
delete(i) | O(log n) | decrease_key + pop |
build_heap(arr) | O(n) | Bottom-up heapify |
Summary
Min-heap: parent ≤ children, minimum always at root.
- Insert: Append to end, sift up — O(log n)
- Extract min: Swap root with last, sift down — O(log n)
- Build from array: Bottom-up heapify — O(n)
- All sift operations: O(log n) = O(tree height) = O(log n) for complete binary tree
- Python's
heapq: Already implements min-heap — use it in practice
*Next Lesson: Max Heap*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Min Heap — Complete Implementation with All Operations.
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, heaps, min, heap
Related Data Structures & Algorithms Topics
Continue learning this concept
HeapsHeap — Complete Introduction to the Priority-Based Tree Data StructureA thorough introduction to heaps — what a heap is, the complete binary tree property, min-heap and max-heap definitions, the heap property with visual examples, heap vs BST, array representation with index formulas, real-world applications, and a roadmap through all heap operations.HeapsHeap Operations — Complete Reference with Complexity AnalysisComplete reference for all heap operations — push, pop, peek, heapify, decrease/increase key, delete arbitrary, merge heaps, and find Kth element. Each operation explained with algorithm, step-by-step trace, implementation, and formal complexity proof.HeapsHeap Problems — 8 Classic Interview Problems with Complete SolutionsSolve 8 classic heap interview problems — kth largest, top K frequent words, merge K lists, reorganize string, IPO (max capital), find median from data stream, smallest range covering K lists, and minimum cost to connect ropes.HeapsMax Heap — Complete Implementation and ApplicationsMaster the max-heap with complete implementation — insert with sift-up, extract maximum with sift-down, Python workaround using negation, in-place heap sort, max-heap for sliding window maximum, and the kth largest element problem.HeapsPriority Queue Using Heap — Implementation, Applications, and PatternsMaster priority queues built on heaps — complete Python and Java implementations, DijkstraSortingHeap Sort — Guaranteed O(n log n) with O(1) SpaceMaster 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.