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
Complete 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.
Operation 1 — Push (Insert)
Algorithm: Add to end, sift up.
Example
def push(heap, value):
heap.append(value)
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[i] < heap[parent]: # Min-heap: swap if child < parent
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
else:
break
Why append + sift-up?
- Appending at the end maintains the complete binary tree shape
- Sift-up restores the heap-order property
- At most log n swaps (one per level)
Time: O(log n) — height of tree
Operation 3 — Peek
Example
def peek(heap):
if not heap:
raise IndexError("Empty heap")
return heap[0] # Root is always min (or max)
Time: O(1) — the heap property guarantees min/max at index 0.
Operation 4 — Heapify (Build Heap from Array)
Algorithm: Start from last non-leaf, sift down each node.
python example
def heapify(arr):
n = len(arr)
# Last non-leaf is at index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)
return arrWhy start from the middle?
- Leaf nodes (indices n//2 to n-1) are trivially valid heaps
- Start heapifying from the last node that has at least one child
Why O(n)?
Intuition: most sift-downs are cheap (nodes near the bottom have little height):
- ~n/2 nodes at height 0 (leaves): 0 work
- ~n/4 nodes at height 1: 1 swap each
- ~n/8 nodes at height 2: 2 swaps each
- ~1 node at height log n: log n swaps
Total ≤ Σ (n/2^(h+1)) × h = n × Σ h/2^(h+1) = n × 1 = O(n)
Operation 5 — Decrease Key
Purpose: Lower a value at index i (in min-heap: this may violate parent constraint).
Example
def decrease_key(heap, i, new_value):
"""
Replace heap[i] with new_value (must be ≤ current value).
Then sift up to restore heap property.
Used in Dijkstra's algorithm to update distances.
"""
if new_value > heap[i]:
raise ValueError("New value must be ≤ current")
heap[i] = new_value
# Sift up: smaller value may violate parent constraint
while i > 0:
parent = (i - 1) // 2
if heap[i] < heap[parent]:
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
else:
break
Time: O(log n)
Usage in Dijkstra:
Example
When relaxing edge (u, v):
if dist[v] > dist[u] + weight(u,v):
dist[v] = dist[u] + weight(u,v)
decrease_key(heap, v_pos_in_heap, dist[v])
Operation 6 — Increase Key
Example
def increase_key(heap, i, new_value):
"""
Replace heap[i] with new_value (must be ≥ current for min-heap).
Then sift DOWN to restore heap property.
"""
if new_value < heap[i]:
raise ValueError("New value must be ≥ current")
heap[i] = new_value
sift_down(heap, len(heap), i) # Larger value may violate child constraint
Operation 7 — Delete Arbitrary Element
python example
def delete_at(heap, i):
"""
Delete element at index i.
Strategy: decrease key to -∞, then pop.
O(log n)
"""
decrease_key(heap, i, float('-inf'))
return pop(heap) # -∞ bubbles to root, then gets poppedAlternative: Replace with last element, then sift up OR down:
Example
def delete_at_v2(heap, i):
"""Replace with last, then sift in appropriate direction."""
heap[i] = heap[-1]
heap.pop()
if i < len(heap):
# Try sift up (if new value < parent)
parent = (i - 1) // 2
if i > 0 and heap[i] < heap[parent]:
# Need to sift up
while i > 0 and heap[i] < heap[(i-1)//2]:
p = (i-1)//2
heap[i], heap[p] = heap[p], heap[i]
i = p
else:
# Need to sift down
sift_down(heap, len(heap), i)
Operation 8 — Replace (Pop + Push Combined)
Example
def replace(heap, value):
"""
Remove and return min/max, then insert new value.
More efficient than pop() + push() because it's one operation.
O(log n) but with smaller constant factor.
"""
if not heap:
raise IndexError("Empty heap")
old_min = heap[0]
heap[0] = value # Place new value at root
sift_down(heap, len(heap), 0) # Sift down once
return old_min
# Used in: streaming problems where you discard old min and add new element
Operation 9 — Merge Two Heaps
python example
def merge_heaps(h1, h2):
"""
Merge two heaps. O(n + m) where n, m = sizes.
Simply concatenate and heapify.
Note: For advanced applications, Fibonacci heaps or Binomial heaps
support O(log n) merge, but they're much more complex.
"""
merged = h1 + h2
heapify(merged)
return mergedOperation 10 — Find Kth Minimum
Example
def kth_minimum(heap, k):
"""
Find kth minimum without destroying the heap.
Method 1: Copy heap, pop k times — O(k log n)
Method 2: BFS on heap — O(k log k)
"""
import heapq
# BFS on heap: explore k levels using a secondary heap
# Secondary heap stores (value, original_index)
result = None
secondary = [(heap[0], 0)] # (value, index in original heap)
visited = set()
for _ in range(k):
val, idx = heapq.heappop(secondary)
result = val
# Add children of idx to secondary heap
l, r = 2*idx+1, 2*idx+2
if l < len(heap) and l not in visited:
heapq.heappush(secondary, (heap[l], l))
visited.add(l)
if r < len(heap) and r not in visited:
heapq.heappush(secondary, (heap[r], r))
visited.add(r)
return result
Complete Complexity Reference
| Operation | Time | Space | Notes |
|---|---|---|---|
| Push | O(log n) | O(1) | Sift up from leaf |
| Pop | O(log n) | O(1) | Sift down from root |
| Peek | O(1) | O(1) | Root access |
| Heapify | O(n) | O(1) | Bottom-up sift-down |
| Decrease Key | O(log n) | O(1) | Sift up |
| Increase Key | O(log n) | O(1) | Sift down |
| Delete at i | O(log n) | O(1) | Decrease to -∞ + pop |
| Replace | O(log n) | O(1) | Faster than pop + push |
| Merge (naive) | O(n + m) | O(n + m) | Concatenate + heapify |
| Merge (advanced)* | O(log n) | — | Fibonacci/Binomial heap |
*Advanced heap structures (not standard binary heap)
Python heapq Module Summary
Example
import heapq
h = [3, 1, 4, 1, 5, 9]
heapq.heapify(h) # O(n): convert list to heap in-place
heapq.heappush(h, 2) # O(log n): push
min_val = heapq.heappop(h) # O(log n): pop minimum
min_val = h[0] # O(1): peek (don't pop)
# Get k smallest/largest (uses heap internally)
heapq.nsmallest(k, h) # O(n log k)
heapq.nlargest(k, h) # O(n log k)
# Push + Pop in one operation (more efficient)
heapq.heappushpop(h, val) # Push val, then pop min
heapq.heapreplace(h, val) # Pop min first, then push val (faster for decreasing)
Summary
All heap operations follow the same pattern:
- Make a structural change (insert at end, remove root, replace value)
- Restore heap order by sifting in the appropriate direction:
- Value decreased or inserted: sift UP (may violate parent)
- Value increased or moved to root: sift DOWN (may violate children)
- Each sift touches at most one node per level → O(log n) per operation
The only exception is heapify which achieves O(n) by starting bottom-up.
*Next Lesson: Heap Problems*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap Operations — Complete Reference with Complexity Analysis.
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, heap, operations
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 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.HeapsMin Heap — Complete Implementation with All OperationsMaster 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.HeapsPriority Queue Using Heap — Implementation, Applications, and PatternsMaster priority queues built on heaps — complete Python and Java implementations, DijkstraArraysArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesA complete deep-dive into every array operation: traversal, insertion, deletion, searching, updating, sorting, merging, and rotating — with Python and Java implementations, time and space complexity for each, and important edge cases to handle.