Java Notes
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.
Min Heap: Every parent node is less than or equal to its children. The root contains the minimum value.
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
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
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.
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
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
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
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
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
Time: O(n log k), Space: O(k)
Application 2: Top K Frequent Elements
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
Application 3: Merge K Sorted Arrays
Try it in WoHoCode
Edit the program, then run it here.
Run this example to see its output.
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.
Continue the lesson path