Chapter 19
Heap in Java
Java Data Structures & Algorithms Series
A Heap is a complete binary tree that satisfies the heap property — in a Min-Heap every parent is
smaller than its children; in a Max-Heap every parent is larger. It is the most efficient data structure
for repeatedly finding the minimum or maximum element.
1 Heap Visualized
We'll use both Min and Max-Heap examples throughout so you can compare behaviour clearly.
Min-Heap (parent ≤ children)
1
/ \
3 2
/ \ / \
7 4 5 6
Array representation: [1, 3, 2, 7, 4, 5, 6]
Max-Heap (parent ≥ children)
9
/ \
7 8
/ \ / \
4 5 2 3
Array representation: [9, 7, 8, 4, 5, 2, 3]
⭐ Key Insight: A heap is stored as an array — no pointers needed.
For node at index i:
Left child → 2*i + 1
Right child → 2*i + 2
Parent → (i - 1) / 2
2 Java's Built-in PriorityQueue
Java provides PriorityQueue which is a Min-Heap by default. For Max-Heap, use a custom
comparator.
import [Link].*;
// Min-Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](5);
[Link](1);
[Link](3);
[Link]([Link]()); // 1 (minimum)
[Link]([Link]()); // 1 (removes minimum)
[Link]([Link]()); // 3
// Max-Heap (reverse order comparator)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
[Link](5);
[Link](1);
[Link](3);
[Link]([Link]()); // 5 (maximum)
Key operations & complexity:
add(x) → O(log n)
peek() → O(1) — view top without removing
poll() → O(log n) — remove top
size() → O(1)
3 Build Heap from Scratch (Heapify)
Understanding internals makes you a stronger problem solver. Let's build a Min-Heap manually.
public class MinHeap {
private int[] heap;
private int size;
private int capacity;
public MinHeap(int capacity) {
[Link] = capacity;
[Link] = 0;
[Link] = new int[capacity];
}
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 at end, bubble up
public void insert(int val) {
heap[size] = val;
int i = size++;
while (i > 0 && heap[i] < heap[parent(i)]) {
swap(i, parent(i));
i = parent(i);
}
}
// EXTRACT MIN: remove root, put last element at root, bubble down
public int extractMin() {
int min = heap[0];
heap[0] = heap[--size];
heapifyDown(0);
return min;
}
private void heapifyDown(int i) {
int smallest = i;
int l = leftChild(i), r = rightChild(i);
if (l < size && heap[l] < heap[smallest]) smallest = l;
if (r < size && heap[r] < heap[smallest]) smallest = r;
if (smallest != i) {
swap(i, smallest);
heapifyDown(smallest);
}
}
public int peek() { return heap[0]; }
public int size() { return size; }
}
// insert: O(log n) | extractMin: O(log n) | peek: O(1)
Build Heap from Array — O(n) Heapify
// Build a max-heap from an unsorted array in O(n) — NOT O(n log n)
public static void buildHeap(int[] arr) {
int n = [Link];
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(arr, n, i);
}
}
private static void heapifyDown(int[] arr, int n, int i) {
int largest = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapifyDown(arr, n, largest);
}
}
// Time: O(n) — mathematical proof shows sum of work converges to O(n)
4 Heap Sort
Use Max-Heap to sort in ascending order — build heap, then repeatedly extract max.
public static void heapSort(int[] arr) {
int n = [Link];
// Step 1: Build max-heap O(n)
for (int i = n / 2 - 1; i >= 0; i--)
heapifyDown(arr, n, i);
// Step 2: Extract max one by one O(n log n)
for (int i = n - 1; i > 0; i--) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapifyDown(arr, i, 0);
}
}
// Time: O(n log n) | Space: O(1) — in-place sorting!
5 Key Heap Patterns & Problems
🔑 Pattern 1 — Kth Largest Element
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
[Link](num);
if ([Link]() > k)
[Link]();
}
return [Link]();
}
// Time: O(n log k) | Space: O(k)
// Example: [3,2,1,5,6,4], k=2 → answer is 5
🔑 Pattern 2 — Top K Frequent Elements
public static int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int n : nums) [Link](n, [Link](n, 0) + 1);
PriorityQueue<Integer> minHeap =
new PriorityQueue<>((a, b) -> [Link](a) - [Link](b));
for (int num : [Link]()) {
[Link](num);
if ([Link]() > k) [Link]();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = [Link]();
return result;
}
// Time: O(n log k) | Space: O(n)
🔑 Pattern 3 — Merge K Sorted Lists
public static int[] mergeKSortedArrays(int[][] arrays) {
PriorityQueue<int[]> minHeap =
new PriorityQueue<>((a, b) -> a[0] - b[0]);
int totalSize = 0;
for (int i = 0; i < [Link]; i++) {
if (arrays[i].length > 0) {
[Link](new int[]{arrays[i][0], i, 0});
totalSize += arrays[i].length;
}
}
int[] result = new int[totalSize];
int idx = 0;
while (![Link]()) {
int[] curr = [Link]();
result[idx++] = curr[0];
int arrIdx = curr[1], elemIdx = curr[2];
if (elemIdx + 1 < arrays[arrIdx].length)
[Link](new int[]{arrays[arrIdx][elemIdx + 1], arrIdx, elemIdx +
1});
}
return result;
}
// Time: O(n log k) — n total elements, k arrays
🔑 Pattern 4 — Find Median from Data Stream
Two heaps trick — Max-Heap for left half, Min-Heap for right half.
class MedianFinder {
PriorityQueue<Integer> maxHeap; // lower half
PriorityQueue<Integer> minHeap; // upper half
public MedianFinder() {
maxHeap = new PriorityQueue<>([Link]());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
[Link](num);
[Link]([Link]());
if ([Link]() > [Link]())
[Link]([Link]());
}
public double findMedian() {
if ([Link]() > [Link]())
return [Link]();
return ([Link]() + [Link]()) / 2.0;
}
}
// addNum: O(log n) | findMedian: O(1)
//
// addNum(1) → maxHeap:[1], minHeap:[] → median = 1.0
// addNum(2) → maxHeap:[1], minHeap:[2] → median = 1.5
// addNum(3) → maxHeap:[2], minHeap:[3] → median = 2.0
🔑 Pattern 5 — Task Scheduler
public static int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>([Link]());
for (int f : freq) if (f > 0) [Link](f);
int time = 0;
while (![Link]()) {
List<Integer> temp = new ArrayList<>();
for (int i = 0; i <= n; i++) {
if (![Link]()) [Link]([Link]() - 1);
}
for (int t : temp) if (t > 0) [Link](t);
time += [Link]() ? [Link]() : n + 1;
}
return time;
}
// Time: O(n log n) | Space: O(1) — only 26 chars
6 Heap Complexity Summary
Operation Min/Max Heap Java PriorityQueue
Insert O(log n) O(log n)
Peek (min/max) O(1) O(1)
Extract min/max O(log n) O(log n)
Build from array O(n) O(n log n)
Search O(n) O(n)
Delete arbitrary O(log n) O(n)
7 Full Runnable Java Program
import [Link].*;
public class Chapter19Heap {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int[] nums = {5, 3, 8, 1, 9, 2, 7, 4, 6};
for (int n : nums) [Link](n);
[Link]("Sorted (Min-Heap poll): ");
while (![Link]()) [Link]([Link]() + " ");
[Link]();
[Link]("3rd Largest: " + findKthLargest(nums, 3));
int[] arr = {5, 3, 8, 1, 9, 2};
heapSort(arr);
[Link]("Heap Sorted: " + [Link](arr));
int[] freq = {1, 1, 1, 2, 2, 3};
[Link]("Top 2 Frequent: " + [Link](topKFrequent(freq,
2)));
MedianFinder mf = new MedianFinder();
[Link](1); [Link](2);
[Link]("Median after [1,2]: " + [Link]());
[Link](3);
[Link]("Median after [1,2,3]: " + [Link]());
}
static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
[Link](n);
if ([Link]() > k) [Link]();
}
return [Link]();
}
static void heapSort(int[] arr) {
int n = [Link];
for (int i = n / 2 - 1; i >= 0; i--) heapifyDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
heapifyDown(arr, i, 0);
}
}
static void heapifyDown(int[] arr, int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapifyDown(arr, n, largest);
}
}
static int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int n : nums) [Link](n, [Link](n, 0) + 1);
PriorityQueue<Integer> minHeap =
new PriorityQueue<>((a, b) -> [Link](a) - [Link](b));
for (int num : [Link]()) {
[Link](num);
if ([Link]() > k) [Link]();
}
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) res[i] = [Link]();
return res;
}
}
class MedianFinder {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>([Link]());
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
public void addNum(int num) {
[Link](num);
[Link]([Link]());
if ([Link]() > [Link]()) [Link]([Link]());
}
public double findMedian() {
return [Link]() > [Link]()
? [Link]()
: ([Link]() + [Link]()) / 2.0;
}
}
8 Practice Problems for Chapter 19
Solve in this order:
Difficulty Problem
Easy Kth largest element in an array (LeetCode #215)
Easy Last stone weight (LeetCode #1046)
Medium Top K frequent elements (LeetCode #347)
Medium K closest points to origin (LeetCode #973)
Medium Find median from data stream (LeetCode #295)
Medium Task scheduler (LeetCode #621)
Hard Merge K sorted lists (LeetCode #23)
Hard Sliding window maximum (LeetCode #239)
💡 Key Insight: The two-heap pattern (MedianFinder) and the min-heap of size K pattern (Kth
Largest) are among the most frequently asked patterns in FAANG interviews. Once you master
these, Chapter 20 — Graphs is next, where heaps power Dijkstra's shortest path algorithm
directly! 🚀