Heap Operations in Java
In Java, Heap operations are typically performed using the PriorityQueue class,
which implements a Min Heap by default.
---
1 Creating a Min Heap:
Javas PriorityQueue is a Min Heap by default, meaning the smallest element is at the top.
```java
import [Link].*;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](10);
[Link](4);
[Link](15);
[Link](1);
[Link]([Link]()); // 1 (Removes smallest)
[Link]([Link]()); // 4 (Next smallest)
}
}
```
### Heap Methods:
- `add(e)`: Inserts element `e`.
- `offer(e)`: Inserts element `e` (returns false if full).
- `poll()`: Removes and returns the smallest element.
- `peek()`: Returns the smallest element without removing.
- `remove(e)`: Removes a specific element.
- `size()`: Returns the number of elements.
- `isEmpty()`: Checks if the heap is empty.
- `clear()`: Removes all elements.
---
2 Creating a Max Heap:
Java does not provide a built-in Max Heap, but we can use a custom Comparator.
```java
import [Link].*;
public class MaxHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
[Link](10);
[Link](4);
[Link](15);
[Link](1);
[Link]([Link]()); // 15 (Removes largest)
[Link]([Link]()); // 10 (Next largest)
}
}
```
---
3 Min Heap for Custom Objects:
```java
import [Link].*;
class Student implements Comparable<Student> {
String name;
int marks;
public Student(String name, int marks) {
[Link] = name;
[Link] = marks;
}
@Override
public int compareTo(Student s) {
return [Link] - [Link]; // Min Heap (sort by marks)
}
}
public class CustomMinHeap {
public static void main(String[] args) {
PriorityQueue<Student> studentHeap = new PriorityQueue<>();
[Link](new Student("Alice", 85));
[Link](new Student("Bob", 75));
[Link](new Student("Charlie", 95));
[Link]([Link]().name); // Output: Bob (Lowest marks)
}
}
```
---
4 Max Heap for Custom Objects:
```java
import [Link].*;
class Student {
String name;
int marks;
public Student(String name, int marks) {
[Link] = name;
[Link] = marks;
}
}
public class CustomMaxHeap {
public static void main(String[] args) {
PriorityQueue<Student> maxHeap = new PriorityQueue<>((a, b) -> [Link] - [Link]);
[Link](new Student("Alice", 85));
[Link](new Student("Bob", 75));
[Link](new Student("Charlie", 95));
[Link]([Link]().name); // Output: Charlie (Highest marks)
}
}
```
---
5 Heap Sort using PriorityQueue:
```java
import [Link].*;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 1, 2};
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
[Link](num);
}
while (![Link]()) {
[Link]([Link]() + " "); // Sorted Order
}
}
}
```
---
### Summary
Use `PriorityQueue<Integer>` for Min Heap (default).
Use `PriorityQueue<Integer>([Link]())` for Max Heap.
Use `Comparator` or `Comparable` for custom objects.
Use `PriorityQueue` for Heap Sort.
