Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Heap data structure in Java covering Min Heap, Max Heap, heap operations, heapify algorithm, PriorityQueue class, heap sort, and applications with detailed implementations.
What is a Heap?
A Heap is a specialized complete binary tree that satisfies the heap property. It is the most efficient data structure for implementing priority queues — where you need quick access to the minimum or maximum element.
Types of Heaps
Max Heap: Every parent node is greater than or equal to its children. The root contains the maximum value.
Example
90
/ \
80 70
/ \ / \
60 50 40 30
Min Heap: Every parent node is less than or equal to its children. The root contains the minimum value.
Example
10
/ \
20 30
/ \ / \
40 50 60 70
Key Properties
| Property | Description |
|---|---|
| Complete Binary Tree | All levels fully filled except possibly last (filled left to right) |
| Heap Property | Parent ≥ children (max-heap) or Parent ≤ children (min-heap) |
| NOT sorted | Only parent-child relationship is maintained, not sibling order |
| Array-based | Efficiently stored as an array without pointers |
Array Representation
A complete binary tree can be stored in an array using index relationships:
| - Parent | (i - 1) / 2 |
| - Left Child | 2 * i + 1 |
| - Right Child | 2 * i + 2 |
| Max Heap | [90, 80, 70, 60, 50, 40, 30] |
| Index | [0] [1] [2] [3] [4] [5] [6] |
| Tree | 90(0) |
Verification:
- Parent of index 4: (4-1)/2 = 1 → value 80 ✓ (80 > 50)
- Children of index 1: 2×1+1=3, 2×1+2=4 → values 60, 50 ✓ (80 > both)
Implementing a Max Heap from Scratch
Example
import java.util.Arrays;
public class MaxHeap {
private int[] heap;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
}
// Helper methods
private int parent(int i) { return (i - 1) / 2; }
private int leftChild(int i) { return 2 * i + 1; }
private int rightChild(int i) { return 2 * i + 2; }
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
// INSERT: Add element and bubble up
public void insert(int value) {
if (size == capacity) throw new RuntimeException("Heap is full");
heap[size] = value;
int current = size;
size++;
// Sift up: swap with parent while larger than parent
while (current > 0 && heap[current] > heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
// EXTRACT MAX: Remove and return the root
public int extractMax() {
if (size == 0) throw new RuntimeException("Heap is empty");
int max = heap[0];
heap[0] = heap[size - 1]; // Move last element to root
size--;
heapifyDown(0); // Restore heap property
return max;
}
// PEEK: View maximum without removing
public int peek() {
if (size == 0) throw new RuntimeException("Heap is empty");
return heap[0];
}
// Heapify down: fix violation at index i
private void heapifyDown(int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapifyDown(largest); // Recurse on affected subtree
}
}
public int getSize() { return size; }
public void printHeap() {
System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
}
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(10);
int[] values = {40, 20, 60, 10, 50, 30, 70};
System.out.println("Inserting: " + Arrays.toString(values));
for (int val : values) {
heap.insert(val);
}
System.out.print("Heap array: ");
heap.printHeap();
System.out.println("Max (peek): " + heap.peek());
System.out.println("\nExtracting elements in order:");
while (heap.getSize() > 0) {
System.out.print(heap.extractMax() + " ");
}
System.out.println();
}
}
Output
Inserting: [40, 20, 60, 10, 50, 30, 70] Heap array: [70, 50, 60, 10, 20, 30, 40] Max (peek): 70 Extracting elements in order: 70 60 50 40 30 20 10
Step-by-Step Insert Operation
Inserting 50 into Max Heap [70, 40, 60, 10, 20, 30]:
| Step 1 | Add 50 at end (index 6) |
| Tree | 70 |
| Step 2 | Compare 50 with parent (60 at index 2) |
| 50 < 60 | No swap needed. DONE! |
| Final | [70, 40, 60, 10, 20, 30, 50] |
Inserting 80 into Max Heap [70, 40, 60, 10, 20, 30]:
| Step 1 | Add 80 at end (index 6) |
| Step 2 | Compare 80 with parent 60 (index 2) |
| 80 > 60 | Swap! |
| Step 3 | Compare 80 with parent 70 (index 0) |
| 80 > 70 | Swap! |
| Step 4 | Index 0, no parent. DONE! |
| Final | [80, 40, 70, 10, 20, 30, 60] |
Time Complexity of Insert: O(log n) — at most traverse the height of the tree.
Step-by-Step Extract Max Operation
Extracting max from [80, 40, 70, 10, 20, 30, 60]:
| Step 1 | Save max = 80 |
| Step 2 | Move last element (60) to root |
| Step 3 | Heapify down from root |
| Compare 60 with children | left=40, right=70 |
| 70 is largest | Swap 60 and 70 |
| Step 4 | Continue heapifying at new position of 60 (index 2) |
| Compare 60 with children | left=30 (index 5) |
| 60 > 30 | No swap. DONE! |
| Final | [70, 40, 60, 10, 20, 30] |
| Extracted | 80 |
Time Complexity of Extract: O(log n)
Java PriorityQueue (Built-in Heap)
Java provides PriorityQueue in java.util — a min-heap by default.
java example
import java.util.PriorityQueue;
import java.util.Collections;
public class PriorityQueueDemo {
public static void main(String[] args) {
// MIN HEAP (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(40);
minHeap.add(20);
minHeap.add(60);
minHeap.add(10);
minHeap.add(50);
System.out.println("Min Heap - peek: " + minHeap.peek());
System.out.print("Min Heap - poll all: ");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " ");
}
System.out.println();
// MAX HEAP (using reverse comparator)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(40);
maxHeap.add(20);
maxHeap.add(60);
maxHeap.add(10);
maxHeap.add(50);
System.out.println("\nMax Heap - peek: " + maxHeap.peek());
System.out.print("Max Heap - poll all: ");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " ");
}
System.out.println();
}
}Output
Min Heap - peek: 10 Min Heap - poll all: 10 20 40 50 60 Max Heap - peek: 60 Max Heap - poll all: 60 50 40 20 10
PriorityQueue Methods
| Method | Description | Time |
|---|---|---|
add(e) / offer(e) | Insert element | O(log n) |
peek() | View top without removing | O(1) |
poll() | Remove and return top | O(log n) |
remove(obj) | Remove specific element | O(n) |
size() | Number of elements | O(1) |
isEmpty() | Check if empty | O(1) |
Heap Sort
Heap Sort uses a max-heap to sort an array in ascending order.
Algorithm:
- Build a max-heap from the array
- Repeatedly extract the max and place it at the end
Example
import java.util.Arrays;
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// Step 1: Build max-heap (heapify from last non-leaf to root)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Step 2: Extract elements one by one
for (int i = n - 1; i > 0; i--) {
// Move current root (max) to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify reduced heap
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, heapSize, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7, 3, 1, 9};
System.out.println("Original: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("Sorted: " + Arrays.toString(arr));
}
}
Output
Original: [12, 11, 13, 5, 6, 7, 3, 1, 9] Sorted: [1, 3, 5, 6, 7, 9, 11, 12, 13]
Time Complexity: O(n log n) — guaranteed, no worst case degradation Space Complexity: O(1) — in-place sorting Not Stable: Equal elements may change relative order
Applications of Heap
Application 1: Kth Largest Element
java example
import java.util.PriorityQueue;
public class KthLargest {
public static int findKthLargest(int[] nums, int k) {
// Use min-heap of size k
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove smallest — keep only k largest
}
}
return minHeap.peek(); // Top of min-heap = kth largest
}
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
System.out.println("Array: " + java.util.Arrays.toString(nums));
System.out.println("2nd largest: " + findKthLargest(nums, 2));
System.out.println("4th largest: " + findKthLargest(nums, 4));
}
}Output
Array: [3, 2, 1, 5, 6, 4] 2nd largest: 5 4th largest: 3
Time: O(n log k), Space: O(k)
Application 2: Top K Frequent Elements
java example
import java.util.*;
public class TopKFrequent {
public static List<Integer> topKFrequent(int[] nums, int k) {
// Count frequencies
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Min-heap of size k (sorted by frequency)
PriorityQueue<Map.Entry<Integer, Integer>> heap =
new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
heap.add(entry);
if (heap.size() > k) {
heap.poll();
}
}
List<Integer> result = new ArrayList<>();
while (!heap.isEmpty()) {
result.add(heap.poll().getKey());
}
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3, 3, 3, 3, 4};
int k = 2;
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Top " + k + " frequent: " + topKFrequent(nums, k));
}
}Output
Array: [1, 1, 1, 2, 2, 3, 3, 3, 3, 4] Top 2 frequent: [3, 1]
Application 3: Merge K Sorted Arrays
Example
import java.util.*;
public class MergeKSorted {
public static int[] mergeKArrays(int[][] arrays) {
// Min-heap: [value, arrayIndex, elementIndex]
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int totalSize = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) {
heap.add(new int[]{arrays[i][0], i, 0});
totalSize += arrays[i].length;
}
}
int[] result = new int[totalSize];
int idx = 0;
while (!heap.isEmpty()) {
int[] top = heap.poll();
result[idx++] = top[0];
int arrIdx = top[1];
int elemIdx = top[2] + 1;
if (elemIdx < arrays[arrIdx].length) {
heap.add(new int[]{arrays[arrIdx][elemIdx], arrIdx, elemIdx});
}
}
return result;
}
public static void main(String[] args) {
int[][] arrays = {{1, 4, 7}, {2, 5, 8}, {3, 6, 9}};
System.out.println("Input arrays:");
for (int[] arr : arrays) {
System.out.println(" " + Arrays.toString(arr));
}
int[] merged = mergeKArrays(arrays);
System.out.println("Merged: " + Arrays.toString(merged));
}
}
Output
Input arrays: [1, 4, 7] [2, 5, 8] [3, 6, 9] Merged: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Time: O(N log k) where N is total elements and k is number of arrays.
Time Complexity Summary
| Operation | Time Complexity |
|---|---|
| Insert (add) | O(log n) |
| Extract Min/Max (poll) | O(log n) |
| Peek (get min/max) | O(1) |
| Build Heap (from array) | O(n) |
| Heap Sort | O(n log n) |
| Delete arbitrary | O(n) for search + O(log n) for fix |
| Search | O(n) — heap is not optimized for search |
Heap vs Other Data Structures
| Operation | Sorted Array | BST | Heap |
|---|---|---|---|
| Find Min/Max | O(1) | O(log n) | O(1) |
| Insert | O(n) | O(log n) | O(log n) |
| Delete Min/Max | O(1)* | O(log n) | O(log n) |
| Search | O(log n) | O(log n) | O(n) |
*Requires shifting elements
Use Heap when: You need efficient insert AND extract-min/max, but DON'T need arbitrary search.
Common Mistakes
- Forgetting PriorityQueue is min-heap — use
Collections.reverseOrder()for max-heap - Assuming heap is sorted — only the root is guaranteed to be min/max
- Off-by-one in index formulas — parent, left, right formulas depend on 0-based or 1-based indexing
- Not calling heapify after removing — heap property must be restored
- Using remove() expecting O(log n) — PriorityQueue.remove(Object) is O(n)
- Building heap in O(n log n) — build-heap from array is O(n), not O(n log n)
Best Practices
- Use Java's PriorityQueue for production code — well-tested and optimized
- Choose min-heap for "k largest" problems — counter-intuitive but correct
- Pre-allocate capacity when size is known:
new PriorityQueue<>(capacity) - Use custom Comparator for complex objects
- Build heap bottom-up (O(n)) instead of n insertions (O(n log n))
- Consider heap for streaming — when elements arrive one at a time
- Remember heap sort is in-place but not stable
Interview Questions
Q1: What is a Heap? A complete binary tree satisfying the heap property (parent ≥ children for max-heap, parent ≤ children for min-heap), typically stored as an array.
Q2: Min-heap vs Max-heap? Min-heap: smallest at root. Max-heap: largest at root. Same structure, opposite ordering.
Q3: Time complexity of building a heap from array? O(n) — using bottom-up heapify. Not O(n log n) as one might expect from n insertions.
Q4: How is a heap different from a BST? BST: left < parent < right (fully ordered, enables search). Heap: parent vs children only (partially ordered, enables quick min/max access).
Q5: Default type of Java PriorityQueue? Min-heap. For max-heap: new PriorityQueue<>(Collections.reverseOrder()).
Q6: Can a heap contain duplicates? Yes. Unlike BST, heaps allow duplicate values.
Q7: Why use array representation for heap? Complete binary tree maps perfectly to array with no wasted space. Parent/child relationships computed by index formulas — no pointers needed.
Q8: What is heapify? The process of restoring the heap property after a violation. Heapify-up (sift-up) after insertion, heapify-down (sift-down) after deletion.
Q9: Is Heap Sort stable? No. Equal elements may change relative order during extraction.
Q10: How to find the kth smallest element efficiently? Use a max-heap of size k. After processing all elements, the root is the kth smallest. Time: O(n log k).
Q11: What is the space complexity of a heap? O(n) for the array. Heap sort is O(1) additional space (in-place).
Q12: Real-world applications of heaps? Priority scheduling (OS), Dijkstra's shortest path, Huffman coding, median maintenance, event-driven simulation, and load balancing.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Heap (DSA).
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, dsa, heap, heap (dsa)
Related Java Master Course Topics
Continue learning this concept
DSA in JavaDynamic Programming in JavaComplete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.DSA in JavaGraph Data Structure in JavaComplete guide to graphs — representation, BFS, DFS, shortest path algorithms, topological sort, and classic graph problems in Java.DSA in JavaHashing in JavaComplete guide to hashing — hash functions, collision resolution, HashMap internals, custom hashCode/equals, and applications of hashing in problem-solving.DSA in JavaLinked List in JavaComplete guide to Linked Lists — Singly, Doubly, and Circular linked lists with Java implementations, operations, and classic interview problems.DSA in JavaQueue in JavaComplete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.DSA in JavaRecursion in JavaMaster recursion — base cases, recursive thinking, call stack visualization, tail recursion, memoization, backtracking, and converting recursion to iteration.