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
Master 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.
Overview of Heap Operations
| Operation | Time Complexity | Description |
|---|---|---|
| Insert | O(log n) | Add element, bubble up to restore heap property |
| Extract max/min | O(log n) | Remove root, replace with last, bubble down |
| Peek | O(1) | Return root element without removing |
| Build heap | O(n) | Convert unordered array into a heap |
| Heapify (sift down) | O(log n) | Fix heap property for a single subtree |
Insert (Bubble Up / Sift Up)
To insert a new element into a max-heap:
- Place the new element at the end of the array (next available position in the complete tree).
- Bubble up: Compare with parent. If larger than parent, swap. Repeat until the element is smaller than its parent or reaches the root.
Dry Run: Insert 60 into Max-Heap
| Initial heap | [50, 30, 40, 20, 25, 35] |
| Step 1 | Append 60 at the end |
| Step 2 | Compare with parent (index (6-1)//2 = 2, value 40) |
| 60 > 40 | swap |
| Step 3 | Compare with parent (index (2-1)//2 = 0, value 50) |
| 60 > 50 | swap |
Python Implementation
Example
def heap_insert(heap, value):
"""Insert value into max-heap."""
heap.append(value)
_bubble_up(heap, len(heap) - 1)
def _bubble_up(heap, index):
"""Move element at index up until heap property is restored."""
while index > 0:
parent = (index - 1) // 2
if heap[index] > heap[parent]:
heap[index], heap[parent] = heap[parent], heap[index]
index = parent
else:
break # heap property satisfied
Extract Max / Delete Root (Bubble Down / Sift Down)
To remove the root (maximum element) from a max-heap:
- Replace the root with the last element in the array.
- Remove the last position (shrink array by 1).
- Bubble down: Compare the new root with its children. Swap with the larger child if it is greater. Repeat until heap property is restored.
Dry Run: Extract Max from [60, 30, 50, 20, 25, 35, 40]
| Step 1 | Save max (60). Replace root with last element (40). Remove last. |
| Step 2 | Compare 40 with children: left=30, right=50. Larger child = 50 (right). |
| 40 < 50 | swap with right child. |
| Step 3 | Compare 40 with children: left=35. (right child index 6 is out of bounds) |
| 40 > 35 | no swap needed. DONE. |
| Result | Extracted 60. New heap: [50, 30, 40, 20, 25, 35] |
| Tree | 50 |
Python Implementation
Example
def heap_extract_max(heap):
"""Remove and return the maximum element."""
if not heap:
raise IndexError("Heap is empty")
max_val = heap[0]
heap[0] = heap[-1] # move last to root
heap.pop() # remove last
if heap:
_bubble_down(heap, 0)
return max_val
def _bubble_down(heap, index):
"""Move element at index down until heap property is restored."""
n = len(heap)
while True:
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < n and heap[left] > heap[largest]:
largest = left
if right < n and heap[right] > heap[largest]:
largest = right
if largest == index:
break # heap property satisfied
heap[index], heap[largest] = heap[largest], heap[index]
index = largest
Build Heap: O(n) from Unordered Array
Given an unordered array, we can convert it into a heap. The naive approach (insert elements one by one) takes O(n log n). But there is a smarter way: bottom-up heapify in O(n).
The Key Insight
Leaves are already valid heaps (single-element heaps). Start from the last internal node and apply bubble-down (heapify) moving upward. Each node is "sifted down" at most to the bottom of its subtree.
Algorithm
- Identify the last internal node: index
(n//2) - 1 - For each node from this index down to 0, call bubble_down.
Dry Run: Build Heap from [4, 10, 3, 5, 1]
| Array | [4, 10, 3, 5, 1] |
| Last internal node | (5//2)-1 = 1 |
| Step 1 | Heapify index 1 (value 10) |
| Children | 5, 1. Largest = 10. No swap needed. |
| Step 2 | Heapify index 0 (value 4) |
| Children | 10, 3. Largest = 10 (left child). |
| Swap 4 and 10 | [10, 4, 3, 5, 1] |
| Children | 5, 1. Largest = 5 (left child). |
| Swap 4 and 5 | [10, 5, 3, 4, 1] |
| Final heap | [10, 5, 3, 4, 1] ✓ (max-heap property satisfied) |
| Tree | 10 |
Python Implementation
Example
def build_max_heap(arr):
"""Convert array into max-heap in-place. O(n) time."""
n = len(arr)
# Start from last internal node, go up to root
for i in range(n // 2 - 1, -1, -1):
_bubble_down(arr, i)
return arr
# Test
arr = [4, 10, 3, 5, 1, 7, 8, 2]
build_max_heap(arr)
print(arr) # [10, 5, 8, 4, 1, 7, 3, 2] — valid max-heap
Why Build Heap is O(n), Not O(n log n)
Intuitively, most nodes are near the bottom and barely move. Formally:
- Nodes at height h: at most ⌈n / 2^(h+1)⌉
- Each node at height h does at most h swaps in bubble_down
Total work = Σ (h=0 to log n) of [⌈n/2^(h+1)⌉ × h] = n × Σ (h=0 to ∞) [h / 2^(h+1)] = n × 1 (the series converges to a constant) = O(n)
Half the nodes are leaves (height 0, zero work). A quarter are at height 1 (one swap max). Only one node (root) might travel the full log n distance.
C++ Implementation
Example
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class MaxHeap {
vector<int> data;
void bubbleUp(int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (data[idx] > data[parent]) {
swap(data[idx], data[parent]);
idx = parent;
} else break;
}
}
void bubbleDown(int idx) {
int n = data.size();
while (true) {
int largest = idx;
int left = 2 * idx + 1, right = 2 * idx + 2;
if (left < n && data[left] > data[largest]) largest = left;
if (right < n && data[right] > data[largest]) largest = right;
if (largest == idx) break;
swap(data[idx], data[largest]);
idx = largest;
}
}
public:
void insert(int val) {
data.push_back(val);
bubbleUp(data.size() - 1);
}
int extractMax() {
int maxVal = data[0];
data[0] = data.back();
data.pop_back();
if (!data.empty()) bubbleDown(0);
return maxVal;
}
int peek() { return data[0]; }
int size() { return data.size(); }
// Build heap from array
MaxHeap(vector<int>& arr) : data(arr) {
for (int i = data.size() / 2 - 1; i >= 0; i--)
bubbleDown(i);
}
MaxHeap() {}
};
int main() {
vector<int> arr = {4, 10, 3, 5, 1, 7, 8, 2};
MaxHeap heap(arr);
cout << "Max: " << heap.extractMax() << endl; // 10
cout << "Max: " << heap.extractMax() << endl; // 8
heap.insert(15);
cout << "Max: " << heap.peek() << endl; // 15
}
Decrease/Increase Key
To change a key's value:
- Increase key (max-heap): Update value, then bubble up (it might now be larger than parent).
- Decrease key (max-heap): Update value, then bubble down (it might now be smaller than children).
Example
def increase_key(heap, index, new_value):
"""Increase value at index and fix heap (max-heap)."""
if new_value < heap[index]:
raise ValueError("New value is smaller than current")
heap[index] = new_value
_bubble_up(heap, index)
def decrease_key(heap, index, new_value):
"""Decrease value at index and fix heap (max-heap)."""
heap[index] = new_value
_bubble_down(heap, index)
Operation Summary
| INSERT: Place at end | Bubble UP |
| EXTRACT MAX/MIN: Swap root with last | Remove last → Bubble DOWN |
| BUILD HEAP: For each internal node (bottom-up) | Bubble DOWN |
| INCREASE KEY: Update value | Bubble UP |
| DECREASE KEY: Update value | Bubble DOWN |
The two fundamental primitives are bubble-up and bubble-down. Every operation reduces to one of them.
Key Takeaways
Heap operations revolve around two movements: bubble up (for inserts and key increases) and bubble down (for extractions and key decreases). The build-heap operation achieves O(n) by exploiting the fact that most nodes have small heights. Understanding these operations deeply is essential for implementing priority queues, heap sort, and graph algorithms like Dijkstra's.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap 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, heap, operations
Related Data Structures & Algorithms Topics
Continue learning this concept
HeapsHeap Data StructureUnderstand the heap data structure — complete binary tree property, max-heap and min-heap invariants, array representation, and parent/child index formulas.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.ArraysArray Operations - Insert, Delete, SearchMaster fundamental array operations including insertion, deletion, and searching.