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
Complete max-heap implementation from scratch — extract-max, increase-key, heap sort connection, and practical applications with full working code.
Max-Heap Definition
A max-heap is a complete binary tree where every node's value is greater than or equal to the values of its children. The root always contains the maximum element, accessible in O(1).
Example
Valid Max-Heap: NOT a Max-Heap:
90 90
/ \ / \
70 80 70 80
/ \ / \ / \ / \
50 60 40 30 50 95 40 30
↑ child > parent (70)!
Complete Max-Heap Class Implementation
Example
class MaxHeap:
def __init__(self):
self.heap = []
def __len__(self):
return len(self.heap)
def __bool__(self):
return len(self.heap) > 0
def _parent(self, i):
return (i - 1) // 2
def _left(self, i):
return 2 * i + 1
def _right(self, i):
return 2 * i + 2
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def _sift_up(self, index):
"""Bubble element up to maintain max-heap property."""
while index > 0:
parent = self._parent(index)
if self.heap[index] > self.heap[parent]:
self._swap(index, parent)
index = parent
else:
break
def _sift_down(self, index):
"""Bubble element down to maintain max-heap property."""
n = len(self.heap)
while True:
largest = index
left = self._left(index)
right = self._right(index)
if left < n and self.heap[left] > self.heap[largest]:
largest = left
if right < n and self.heap[right] > self.heap[largest]:
largest = right
if largest == index:
break
self._swap(index, largest)
index = largest
def insert(self, value):
"""Insert a new element. O(log n)."""
self.heap.append(value)
self._sift_up(len(self.heap) - 1)
def peek(self):
"""Return maximum element without removing. O(1)."""
if not self.heap:
raise IndexError("Heap is empty")
return self.heap[0]
def extract_max(self):
"""Remove and return the maximum element. O(log n)."""
if not self.heap:
raise IndexError("Heap is empty")
max_val = self.heap[0]
last = self.heap.pop()
if self.heap:
self.heap[0] = last
self._sift_down(0)
return max_val
def increase_key(self, index, new_value):
"""Increase the value at index. O(log n)."""
if new_value < self.heap[index]:
raise ValueError(f"New value {new_value} is less than current {self.heap[index]}")
self.heap[index] = new_value
self._sift_up(index)
def delete(self, index):
"""Delete element at arbitrary index. O(log n)."""
# Increase to infinity, then extract max
self.heap[index] = float('inf')
self._sift_up(index)
self.extract_max()
@classmethod
def from_array(cls, arr):
"""Build max-heap from array in O(n) time."""
heap = cls()
heap.heap = arr[:]
n = len(heap.heap)
for i in range(n // 2 - 1, -1, -1):
heap._sift_down(i)
return heap
def __repr__(self):
return f"MaxHeap({self.heap})"
# Demonstration
h = MaxHeap()
for val in [15, 10, 20, 8, 25, 5, 30]:
h.insert(val)
print(f"Insert {val:2d}: {h.heap}")
print(f"\nPeek: {h.peek()}") # 30
print(f"Extract: {h.extract_max()}") # 30
print(f"Extract: {h.extract_max()}") # 25
print(f"Heap: {h.heap}") # [20, 10, 15, 8, 5]
Extract-Max: Step-by-Step
Extract-max is the most important operation — it removes and returns the largest element while maintaining the heap structure.
| Heap | [90, 70, 80, 50, 60, 40, 30] |
| Step 1 | Save 90 (the max). Replace root with last element (30). |
| Step 2 | Sift down 30. |
| Swap | [80, 70, 30, 50, 60, 40] |
| Step 3 | Continue sifting 30 at index 2. |
| 30 < 40 | swap: [80, 70, 40, 50, 60, 30] |
| Step 4 | 30 is at index 5 (leaf). Done. |
| Result | Returned 90. New heap: [80, 70, 40, 50, 60, 30] |
Increase-Key Operation
Increase-key raises a node's value, potentially violating the heap property with its parent. Solution: sift up.
Example
# Example: Increase index 4 from 60 to 95
heap = [80, 70, 40, 50, 60, 30]
# After update: [80, 70, 40, 50, 95, 30]
# 95 > parent 70 → swap: [80, 95, 40, 50, 70, 30]
# 95 > parent 80 → swap: [95, 80, 40, 50, 70, 30]
# 95 at root. Done.
This operation is crucial for priority queue update — when a task's priority increases, it needs to bubble up to the correct position.
Connection to Heap Sort
Heap sort uses a max-heap to sort an array in-place:
- Build a max-heap from the array — O(n)
- Repeatedly extract max: Swap root (max) with the last unsorted element, reduce heap size by 1, sift down the new root — O(n log n) total
Example
def heap_sort(arr):
n = len(arr)
# Phase 1: Build max-heap in-place
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)
# Phase 2: Extract elements one by one
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # move max to end
sift_down(arr, i, 0) # restore heap on reduced array
def sift_down(arr, heap_size, index):
while True:
largest = index
left = 2 * index + 1
right = 2 * index + 2
if left < heap_size and arr[left] > arr[largest]:
largest = left
if right < heap_size and arr[right] > arr[largest]:
largest = right
if largest == index:
break
arr[index], arr[largest] = arr[largest], arr[index]
index = largest
# Test
arr = [4, 10, 3, 5, 1, 7, 8, 2]
heap_sort(arr)
print(arr) # [1, 2, 3, 4, 5, 7, 8, 10]
Heap Sort Dry Run
| Array | [4, 10, 3, 5, 1] |
| After build-heap | [10, 5, 3, 4, 1] |
| Extract 10: swap with last | [1, 5, 3, 4, | 10] |
| Sift down 1: | [5, 4, 3, 1, | 10] |
| Extract 5: swap with last | [1, 4, 3, | 5, 10] |
| Sift down 1: | [4, 1, 3, | 5, 10] |
| Extract 4: swap with last | [3, 1, | 4, 5, 10] |
| Sift down 3: | [3, 1, | 4, 5, 10] (already valid) |
| Extract 3: swap with last | [1, | 3, 4, 5, 10] |
| Final sorted | [1, 3, 4, 5, 10] ✓ |
Heap Sort Properties
| Property | Value |
|---|---|
| Time (all cases) | O(n log n) |
| Space | O(1) — in-place |
| Stable? | No (relative order of equal elements not preserved) |
| Adaptive? | No (same time regardless of input order) |
Heap sort is guaranteed O(n log n) (unlike quicksort's O(n²) worst case) and uses no extra space (unlike merge sort's O(n)).
C++ Complete Implementation
Example
#include <vector>
#include <stdexcept>
#include <iostream>
using namespace std;
class MaxHeap {
vector<int> data;
void siftUp(int i) {
while (i > 0 && data[i] > data[(i-1)/2]) {
swap(data[i], data[(i-1)/2]);
i = (i-1)/2;
}
}
void siftDown(int i, int heapSize) {
while (2*i+1 < heapSize) {
int largest = i;
int l = 2*i+1, r = 2*i+2;
if (l < heapSize && data[l] > data[largest]) largest = l;
if (r < heapSize && data[r] > data[largest]) largest = r;
if (largest == i) break;
swap(data[i], data[largest]);
i = largest;
}
}
public:
void insert(int val) {
data.push_back(val);
siftUp(data.size()-1);
}
int extractMax() {
if (data.empty()) throw runtime_error("Empty heap");
int mx = data[0];
data[0] = data.back();
data.pop_back();
if (!data.empty()) siftDown(0, data.size());
return mx;
}
int peek() const { return data[0]; }
bool empty() const { return data.empty(); }
int size() const { return data.size(); }
void increaseKey(int idx, int val) {
if (val < data[idx]) throw runtime_error("Value too small");
data[idx] = val;
siftUp(idx);
}
// Build from array
MaxHeap(vector<int> arr) : data(move(arr)) {
for (int i = data.size()/2 - 1; i >= 0; i--)
siftDown(i, data.size());
}
MaxHeap() = default;
};
Practical Applications of Max-Heap
- Task scheduling: OS runs highest-priority process first (priority queue)
- Kth largest element: Maintain a min-heap of size K, or use max-heap with K extractions
- Merge K sorted arrays: Though min-heap is more natural for this
- Bandwidth management: Network routers serve highest-priority packets first
- Event simulation: Process events with highest priority/urgency first
- Median in data stream: Max-heap holds the lower half, min-heap the upper half
Key Takeaways
A max-heap keeps the maximum at the root, providing O(1) access and O(log n) extraction. The two core movements — sift up (after insert/increase-key) and sift down (after extract/decrease-key) — maintain the invariant. The heap sort algorithm leverages this to sort in-place in guaranteed O(n log n). Combined with O(n) build-heap, the max-heap is a versatile, efficient structure for priority-based processing.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Max-Heap.
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, max, heap
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 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.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.SortingHeap Sort - Heap Based SortingMaster heap sort using heap data structure for efficient sorting.