class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int capacity) {
heap = new int[capacity];
}
public void insert(int value) {
if(size == heap.length) {
throw new IndexOutOfBoundsException("Heap is full");
}
heap[size] = value;
fixHeapAbove(size);
size++;
}
private void fixHeapAbove(int index) {
int newValue = heap[index];
while(index > 0 && newValue > heap[getParent(index)]) {
heap[index] = heap[getParent(index)];
index = getParent(index);
}
heap[index] = newValue;
}
private int getParent(int index) {
return (index - 1) / 2;
}
}
Let's create a main class to run the MaxHeap implementation. We'll add several items to the heap, and display the structure of the heap after each insertion.
Here's a Main class that showcases usage of MaxHeap:
public class Main {
public static void main(String[] args) {
MaxHeap heap = new MaxHeap(10);
heap.insert(80);
heap.insert(75);
heap.insert(60);
heap.insert(68);
heap.insert(55);
heap.insert(40);
heap.insert(52);
heap.insert(67);
heap.printHeap();
}
}
class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int capacity) {
heap = new int[capacity];
}
public void insert(int value) {
if(size == heap.length) {
throw new IndexOutOfBoundsException("Heap is full");
}
heap[size] = value;
fixHeapAbove(size);
size++;
}
private void fixHeapAbove(int index) {
int newValue = heap[index];
while(index > 0 && newValue > heap[getParent(index)]) {
heap[index] = heap[getParent(index)];
index = getParent(index);
}
heap[index] = newValue;
}
private int getParent(int index) {
return (index - 1) / 2;
}
public void printHeap() {
for(int i=0; i<size; i++) {
System.out.println(heap[i]);
}
}
}
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9};
int k = 3;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num: nums) {
pq.add(num);
if(pq.size()>k) {
pq.poll();
}
}
while(!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
โWhat does the poll method do in priorityqueue
The poll() method is a part of the PriorityQueue class in Java. The PriorityQueue class is a queue data structure implementation where the objects are processed based on their priority. It is different from the standard queue as it implements a priority heap where elements are ordered as per their natural ordering or a custom comparator provided at queue construction time.
The poll() method in PriorityQueue is used to retrieve and remove the head of this queue, or return null if this queue is empty. The head of this PriorityQueue instance is the least element with respect to the specified ordering. If multiple elements are tied for the least value, the head is one of those elements.
Let's understand it with an example:
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(4);
numbers.add(2);
numbers.add(1);
System.out.println("PriorityQueue: " + numbers);
int number = numbers.poll();
System.out.println("Removed Number: " + number);
System.out.println("Updated PriorityQueue: " + numbers);
}
}
How is the priority in a priority queue established
Priority in a PriorityQueue is determined based on the elements' natural ordering or by a Comparator that is provided at PriorityQueue creation time. Let's dive into these two scenarios a bit more:
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
System.out.println(pq.poll()); // Outputs "1"
System.out.println(pq.poll()); // Outputs "3"
System.out.println(pq.poll()); // Outputs "5"
Comparator<Person> ageComparator = new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
return Integer.compare(p1.getAge(), p2.getAge());
}
};
PriorityQueue<Person> pq = new PriorityQueue<>(ageComparator);
pq.add(new Person("Alice", 30));
pq.add(new Person("Bob", 20));
pq.add(new Person("Charlie", 25));
System.out.println(pq.poll().getName()); // Outputs "Bob"
System.out.println(pq.poll().getName()); // Outputs "Charlie"
System.out.println(pq.poll().getName()); // Outputs "Alice"
PriorityQueue: [1, 4, 2]
Removed Number: 1
Updated PriorityQueue: [2, 4]