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 priority queues built on heaps — complete Python and Java implementations, Dijkstra
Priority Queue vs Regular Queue
Regular queue: First In, First Out — always dequeues oldest element. Priority queue: Always dequeues highest priority element, regardless of insertion order.
Example
Regular Queue: [task1, task2, task3] → dequeue task1 (oldest)
Priority Queue: [(task2, priority=10), (task1, priority=3), (task3, priority=7)]
→ dequeue task2 (highest priority)
Binary heaps provide all priority queue operations in O(log n).
Application 1 — Dijkstra's Shortest Path
Example
import heapq
from collections import defaultdict
def dijkstra(graph, source):
"""
Dijkstra's algorithm using priority queue (min-heap).
graph: {node: [(neighbor, weight), ...]}
Time: O((V + E) log V)
"""
dist = defaultdict(lambda: float('inf'))
dist[source] = 0
# Min-heap: (distance, node)
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # Outdated entry (lazy deletion)
for v, w in graph.get(u, []):
new_dist = d + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dict(dist)
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Application 2 — Median of a Data Stream (Two Heaps)
Example
import heapq
class MedianFinder:
"""
Find median of stream using two heaps.
- Max-heap: lower half of data
- Min-heap: upper half of data
Balance: lower half has same or one more element.
Median = top of lower (odd total) or average of both tops (even).
Insert: O(log n), FindMedian: O(1)
"""
def __init__(self):
self.lower = [] # Max-heap (negate for Python's min-heap)
self.upper = [] # Min-heap
def add_num(self, num):
# Add to lower half first (max-heap)
heapq.heappush(self.lower, -num)
# Balance: if lower top > upper bottom, move to upper
if self.upper and -self.lower[0] > self.upper[0]:
heapq.heappush(self.upper, -heapq.heappop(self.lower))
# Balance sizes: lower has at most 1 more than upper
if len(self.lower) > len(self.upper) + 1:
heapq.heappush(self.upper, -heapq.heappop(self.lower))
elif len(self.upper) > len(self.lower):
heapq.heappush(self.lower, -heapq.heappop(self.upper))
def find_median(self):
if len(self.lower) > len(self.upper):
return -self.lower[0] # Odd total: lower has extra
return (-self.lower[0] + self.upper[0]) / 2 # Even total: average
mf = MedianFinder()
for num in [1, 2, 3, 4, 5]:
mf.add_num(num)
print(f"After adding {num}: median = {mf.find_median()}")
# 1, 1.5, 2, 2.5, 3
Application 3 — Task Scheduler (CPU)
Example
import heapq
from collections import Counter
def task_scheduler(tasks, n):
"""
Minimum intervals for CPU with cooldown n between same tasks.
Always execute the most frequent remaining task.
"""
freq = Counter(tasks)
max_heap = [-f for f in freq.values()]
heapq.heapify(max_heap)
time = 0
cooldown_queue = [] # (available_time, neg_freq)
while max_heap or cooldown_queue:
time += 1
# Release tasks that are now available
if cooldown_queue and cooldown_queue[0][0] <= time:
_, f = heapq.heappop(cooldown_queue)
heapq.heappush(max_heap, f)
if max_heap:
freq_left = heapq.heappop(max_heap) + 1 # Decrement (negated)
if freq_left < 0: # Still has remaining instances
heapq.heappush(cooldown_queue, (time + n + 1, freq_left))
# else: idle
return time
print(task_scheduler(["A","A","A","B","B","B"], 2)) # 8
# A→B→idle→A→B→idle→A→B
Application 4 — K-Way Merge
Example
import heapq
def k_way_merge(sorted_lists):
"""
Merge k sorted lists into one sorted list.
Time: O(n log k), Space: O(k)
"""
result = []
heap = [] # (value, list_idx, element_idx)
for i, lst in enumerate(sorted_lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
while heap:
val, li, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(sorted_lists[li]):
heapq.heappush(heap, (sorted_lists[li][ei+1], li, ei+1))
return result
print(k_way_merge([[1,4,7],[2,5,8],[3,6,9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
Application 5 — Event Simulation
Example
import heapq
def simulate_events(events):
"""
Process events in time order using priority queue.
events: list of (time, event_type, data)
"""
event_queue = list(events)
heapq.heapify(event_queue)
results = []
while event_queue:
time, event_type, data = heapq.heappop(event_queue)
print(f"t={time}: {event_type} — {data}")
results.append((time, event_type))
return results
events = [
(5, "SERVER_REQUEST", "req_3"),
(1, "SERVER_START", "server"),
(3, "CLIENT_CONNECT", "client_1"),
(2, "DATABASE_READY", "db"),
]
simulate_events(events)
# t=1: SERVER_START
# t=2: DATABASE_READY
# t=3: CLIENT_CONNECT
# t=5: SERVER_REQUEST
Java's PriorityQueue
java example
import java.util.PriorityQueue;
// Min-heap (natural ordering)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
System.out.println(pq.poll()); // 1 (minimum)
// Max-heap (reverse ordering)
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
maxPQ.offer(5); maxPQ.offer(1); maxPQ.offer(3);
System.out.println(maxPQ.poll()); // 5 (maximum)
// Custom priority: sort by string length
PriorityQueue<String> strPQ = new PriorityQueue<>(Comparator.comparingInt(String::length));
strPQ.offer("banana"); strPQ.offer("cat"); strPQ.offer("ab");
System.out.println(strPQ.poll()); // "ab" (shortest)Summary
Priority queues power a huge range of algorithms:
| Application | Heap Type | Pattern |
|---|---|---|
| Dijkstra's | Min-heap | Always process smallest distance |
| Prim's MST | Min-heap | Always add cheapest edge |
| Huffman Coding | Min-heap | Always merge two smallest frequencies |
| Median Stream | Two heaps | Balance upper and lower halves |
| Top-K | Min-heap of size k | Maintain k largest |
| K-Way Merge | Min-heap | Always take smallest front |
| Task Scheduler | Max-heap | Always execute most frequent |
| Event Simulation | Min-heap | Process earliest event first |
The heap-based priority queue is one of the most versatile data structures — whenever you need to repeatedly identify and process the extreme (minimum or maximum) of a changing collection, a heap is the right tool.
*Next Lesson: Heap Problems*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Priority Queue Using Heap — Implementation, Applications, and Patterns.
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, priority, queue
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.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.QueuesPriority Queue — Complete Guide from Concept to ImplementationMaster priority queues — what they are, how they differ from regular queues, heap-based implementation, Python