DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL 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 Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete 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
Understand the heap data structure — complete binary tree property, max-heap and min-heap invariants, array representation, and parent/child index formulas.
What is a Heap?
A heap is a specialized tree-based data structure that satisfies two properties:
- Shape Property (Complete Binary Tree): Every level is completely filled except possibly the last, which is filled from left to right.
- Heap Property (Ordering): Each node's value has a specific relationship with its children's values.
For a max-heap: every parent is ≥ its children. The maximum element is always at the root. For a min-heap: every parent is ≤ its children. The minimum element is always at the root.
Intuition: The Corporate Hierarchy
Think of a max-heap like a company hierarchy where everyone's salary is higher than their direct reports' salaries. The CEO (root) has the highest salary. Each manager earns more than their subordinates. The lowest-paid employees are at the bottom. If you want to find the highest-paid person, just look at the top — O(1).
The Complete Binary Tree Property
A complete binary tree of height h has:
- All levels 0 through h-1 are completely full
- Level h is filled from left to right (no gaps)
Example
Valid complete binary tree: INVALID (gap in last level):
50 50
/ \ / \
30 40 30 40
/ \ / / \ \
20 25 35 20 25 35
↑ gap before this!
This shape constraint is crucial — it guarantees the tree height is always ⌊log₂(n)⌋, ensuring O(log n) operations.
Array Representation
The brilliant insight of heaps: a complete binary tree maps perfectly to a flat array with no pointers needed. We store elements level by level, left to right.
| Tree | 50 |
| Array (0-indexed) | [50, 30, 40, 20, 25, 35, 10] |
| Index | 0 1 2 3 4 5 6 |
Parent/Child Index Formulas (0-indexed)
For a node at index i:
- Parent:
(i - 1) // 2 - Left child:
2 * i + 1 - Right child:
2 * i + 2
Example
# Verification for index 1 (value 30):
parent = (1 - 1) // 2 = 0 → arr[0] = 50 ✓ (30's parent is 50)
left = 2 * 1 + 1 = 3 → arr[3] = 20 ✓ (30's left child)
right = 2 * 1 + 2 = 4 → arr[4] = 25 ✓ (30's right child)
1-Indexed Variant (Simpler Formulas)
Some implementations use index 1 as root (index 0 unused):
- Parent:
i // 2 - Left child:
2 * i - Right child:
2 * i + 1
Max-Heap vs Min-Heap
Example
Max-Heap (root = max): Min-Heap (root = min):
90 5
/ \ / \
70 80 10 15
/ \ / / \ /
50 60 40 20 30 25
Invariant: parent ≥ children Invariant: parent ≤ children
| Property | Max-Heap | Min-Heap |
|---|---|---|
| Root element | Maximum | Minimum |
| Find max | O(1) | O(n) |
| Find min | O(n) | O(1) |
| Parent vs children | Parent ≥ children | Parent ≤ children |
| Use case | Priority queue (max first) | Priority queue (min first) |
What a Heap is NOT
Common misconceptions:
- Not a BST: In a BST, left < parent < right. In a heap, both children can be less than (max-heap) or greater than (min-heap) the parent. There is NO left/right ordering between siblings.
- Not fully sorted: Only the root-to-leaf paths maintain the heap property. Siblings and cousins have no ordering relationship.
- Not unique: Many valid heaps exist for the same set of elements (unlike a BST with unique structure for unique elements).
Example
Both are valid max-heaps for {50, 30, 40, 20, 25}:
50 50
/ \ / \
30 40 40 30
/ \ / \
20 25 25 20
Properties and Guarantees
| Property | Value |
|---|---|
| Height | ⌊log₂(n)⌋ |
| Number of leaves | ⌈n/2⌉ |
| Number of internal nodes | ⌊n/2⌋ |
| Nodes at level k | min(2^k, n - 2^k + 1) |
| Last internal node index | (n/2) - 1 (0-indexed) |
Why Use a Heap?
Heaps provide an efficient implementation of priority queues — abstract data structures where the highest (or lowest) priority element is served first.
| Operation | Heap | Sorted Array | Unsorted Array |
|---|---|---|---|
| Find max/min | O(1) | O(1) | O(n) |
| Insert | O(log n) | O(n) | O(1) |
| Delete max/min | O(log n) | O(1) or O(n) | O(n) |
| Build from array | O(n) | O(n log n) | O(1) |
Heaps give the best balanced trade-off: fast find, fast insert, fast delete.
Python's heapq Module
Python provides a min-heap through the heapq module:
Example
import heapq
# Create a min-heap
nums = [50, 30, 40, 20, 25, 35, 10]
heapq.heapify(nums) # O(n) — converts list in-place to min-heap
print(nums) # [10, 20, 35, 50, 25, 40, 30] — heap-ordered array
# Insert
heapq.heappush(nums, 5) # O(log n)
print(nums[0]) # 5 — new minimum
# Extract minimum
smallest = heapq.heappop(nums) # O(log n)
print(smallest) # 5
# For max-heap in Python: negate values
max_heap = []
for val in [50, 30, 40, 20]:
heapq.heappush(max_heap, -val)
print(-heapq.heappop(max_heap)) # 50 (the maximum)
C++ Priority Queue
Example
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int main() {
// Max-heap (default in C++)
priority_queue<int> maxHeap;
maxHeap.push(50);
maxHeap.push(30);
maxHeap.push(40);
cout << maxHeap.top() << endl; // 50
maxHeap.pop();
cout << maxHeap.top() << endl; // 40
// Min-heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(50);
minHeap.push(30);
minHeap.push(40);
cout << minHeap.top() << endl; // 30
}
Heap Applications
- Priority queues: OS task scheduling, event-driven simulation
- Heap Sort: O(n log n) in-place sorting algorithm
- Graph algorithms: Dijkstra's shortest path, Prim's MST
- Top-K problems: Find K largest/smallest elements efficiently
- Median maintenance: Two heaps (max + min) maintain running median
- Merge K sorted lists: Min-heap holds the front of each list
Key Takeaways
A heap is a complete binary tree stored as an array, where parents dominate children (max-heap: parent ≥ children, min-heap: parent ≤ children). The array representation eliminates pointer overhead and enables O(1) parent/child navigation via index arithmetic. With O(1) access to the extremal element and O(log n) insert/delete, heaps are the foundational structure behind priority queues — one of the most widely used data structures in practice.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap Data Structure.
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, introduction
Related Data Structures & Algorithms Topics
Continue learning this concept
HeapsHeap OperationsMaster core heap operations — insert with bubble-up, delete with bubble-down, heapify individual nodes, and build a heap in O(n) time from an unordered array.HeapsHeap Interview ProblemsMaster the most common heap-based interview problems: Kth largest element, merge K sorted lists, find median in a stream, and top K frequent elements.HeapsMax-HeapComplete max-heap implementation from scratch — extract-max, increase-key, heap sort connection, and practical applications with full working code.HeapsMin-Heap Implementation and Use CasesComplete guide to min-heap data structure with implementation from scratch, extract-min, decrease-key operations, and connections to DijkstraHeapsPriority Queue using HeapUnderstand the Priority Queue abstract data type, implement it with a binary heap, and explore real-world applications from task scheduling to graph algorithms.ArraysArrays - Fundamental Data StructureLearn array basics, structure, operations, and properties as the foundation of data structures.