1.
Heap Definition
Heap: A heap is a special type of binary tree that satisfies the heap property. There
are two main types:
Min-Heap: In a min-heap, the key at the root node is the smallest among all
keys in the binary tree. The same property must be recursively true for all
sub-trees.
Max-Heap: In a max-heap, the key at the root node is the largest among all
keys in the binary tree. The same property must be recursively true for all
sub-trees.
2. Usage
Min-Heap: Useful for implementing priority queues where you need quick
access to the smallest element. Commonly used in algorithms like Dijkstra's
shortest path.
Max-Heap: Useful for implementing priority queues where you need quick
access to the largest element. Commonly used in algorithms like heap sort.
3. Java Code Examples
Min-Heap
1. Insertion
java
Copy code
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(4);
minHeap.add(7);
System.out.println("Min Heap: " + minHeap); // Output: [4, 10,
7]
}
}
2. Deletion (Remove Minimum Element)
java
Copy code
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(4);
minHeap.add(7);
System.out.println("Removed Min Element: " +
minHeap.poll()); // Output: 4
System.out.println("Min Heap after removal: " + minHeap); //
Output: [7, 10]
}
}
3. Peek (View Minimum Element)
java
Copy code
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(4);
minHeap.add(7);
System.out.println("Minimum Element: " + minHeap.peek()); //
Output: 4
}
}
Max-Heap
1. Insertion
java
Copy code
import java.util.PriorityQueue;
import java.util.Comparator;
public class MaxHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(4);
maxHeap.add(7);
System.out.println("Max Heap: " + maxHeap); // Output: [10, 4,
7]
}
}
2. Deletion (Remove Maximum Element)
java
Copy code
import java.util.PriorityQueue;
import java.util.Comparator;
public class MaxHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(4);
maxHeap.add(7);
System.out.println("Removed Max Element: " +
maxHeap.poll()); // Output: 10
System.out.println("Max Heap after removal: " + maxHeap); //
Output: [7, 4]
}
}
3. Peek (View Maximum Element)
java
Copy code
import java.util.PriorityQueue;
import java.util.Comparator;
public class MaxHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(4);
maxHeap.add(7);
System.out.println("Maximum Element: " + maxHeap.peek()); //
Output: 10
}
}
4. LeetCode Problems
Min-Heap Problem: LeetCode 295: Find Median from Data Stream
Define: Implement a data structure that supports the following operations
efficiently: add a number, and find the median of all numbers added so far.
Code:
java
Copy code
import java.util.*;
class MedianFinder {
private PriorityQueue<Integer> minHeap;
private PriorityQueue<Integer> maxHeap;
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new
PriorityQueue<>(Collections.reverseOrder());
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
}
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
Input Example: [1, 2], [3]
Output Example: 1.5, 2.0
Max-Heap Problem: LeetCode 215: Kth Largest Element in an Array
Define: Find the k-th largest element in an unsorted array.
Code:
java
Copy code
import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
for (int num : nums) {
maxHeap.add(num);
}
for (int i = 1; i < k; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}
}
Input Example: [3,2,1,5,6,4], k = 2
Output Example: 5
These examples should give you a good starting point for working with heaps in
Java and applying them to problems.
Common Terms and Methods
1. PriorityQueue:
o Definition: A queue that orders its elements based on their priority.
By default, it behaves like a min-heap.
o Usage: Useful for efficiently accessing the smallest (min-heap) or
largest (max-heap) element.
o Example: PriorityQueue<Integer> minHeap = new
PriorityQueue<>();
2. Collections.reverseOrder():
o Definition: A comparator that provides a reverse order for sorting.
When used with a PriorityQueue, it creates a max-heap.
o Usage: Used to turn a min-heap into a max-heap by reversing the
order.
o Example: PriorityQueue<Integer> maxHeap = new
PriorityQueue<>(Collections.reverseOrder());
3. poll():
o Definition: Removes and returns the highest-priority element (in a
min-heap, this is the smallest element; in a max-heap, it is the largest).
o Usage: Used to retrieve and remove the root of the heap.
o Example: int min = minHeap.poll();
4. peek():
o Definition: Retrieves, but does not remove, the highest-priority
element.
o Usage: Used to view the root of the heap without altering the heap
structure.
o Example: int min = minHeap.peek();
5. offer():
o Definition: Adds an element to the heap.
o Usage: Used to insert a new element into the priority queue.
o Example: minHeap.offer(10);
6. add():
o Definition: Similar to offer(), it adds an element to the heap.
o Usage: Can be used interchangeably with offer() in PriorityQueue.
o Example: minHeap.add(10);
7. size():
o Definition: Returns the number of elements in the heap.
o Usage: Useful for checking the number of elements present.
o Example: int size = minHeap.size();
8. Comparator:
o Definition: An interface used to define a custom ordering for
elements.
o Usage: Allows customization of sorting order, such as reversing order
or sorting based on specific criteria.
o Example: Comparator<Integer> comp =
Collections.reverseOrder();
Examples in Context
Min-Heap Example
java
Copy code
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(10);
minHeap.offer(4);
minHeap.offer(7);
System.out.println("Min Heap: " + minHeap); // Output: [4, 10,
7]
System.out.println("Removed Min Element: " +
minHeap.poll()); // Output: 4
System.out.println("Min Heap after removal: " + minHeap); //
Output: [7, 10]
}
}
Max-Heap Example
java
Copy code
import java.util.PriorityQueue;
import java.util.Collections;
public class MaxHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new
PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(4);
maxHeap.offer(7);
System.out.println("Max Heap: " + maxHeap); // Output: [10, 4,
7]
System.out.println("Removed Max Element: " +
maxHeap.poll()); // Output: 10
System.out.println("Max Heap after removal: " + maxHeap); //
Output: [7, 4]
}
}
These terms and methods are often used in LeetCode problems that involve heaps
or priority queues. Understanding them will help you effectively solve problems
that require heap operations.
4o mini
