package pep.Day65;
import java.util.ArrayList;
public class Heap {
private ArrayList<Integer> arr;
public Heap(int[] data) {
arr = new ArrayList<>();
for (int i : data) {
arr.add(i);
}
// down heapify: isme last se shuru krenge, and end me 0th index pr sahi mil jaega
for (int i = arr.size() - 1; i >= 0; i--) {
// isme index pass kr denge
// iska operation hona cheye, nlog(n)
// but yeh O(n) hoga: mathematical proof
downHeapify(i);
}
}
public boolean compareTo(int i, int j) {
return arr.get(i) > arr.get(j);
}
public void downHeapify(int parentIndex) {
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
int maxIndex = parentIndex;
// compareTo method if returns:
// positive-> leftChildIndex pr value bade hogi, hence, update maxIndex
if (leftChildIndex < arr.size() && compareTo(leftChildIndex, maxIndex))
maxIndex = leftChildIndex;
// rightChildIndex < arr.size() islea lagaya kyon ki hum upar se niche aa rhe hain
if (rightChildIndex < arr.size() && compareTo(rightChildIndex, maxIndex))
maxIndex = rightChildIndex;
if (maxIndex != parentIndex) {
swap(parentIndex, maxIndex); // jo bhi max hoga usko swap kr denge
downHeapify(maxIndex); // dobara call krenge niche wala tree check krne ke lea
}
}
private void swap(int i, int j) {
int x = arr.get(i);
int y = arr.get(j);
arr.set(i, y);
arr.set(j, x);
}
public int remove() {
int ans = arr.get(0);
swap(0, arr.size() - 1);
arr.remove(arr.size() - 1);
downHeapify(0);
return ans;
}
public void add(int data) {
arr.add(data);
upheapify(arr.size() - 1);
}
private void upheapify(int childIndex) {
// formula to find parentIndex from childIndex:
// parentIndex = (childIndex-1)/2;
int parentIndex = (childIndex - 1) / 2;
// parentIndex >= 0 islea lagae kyon ki hum niche se upar jaa rhe hain
if (parentIndex >= 0 && compareTo(childIndex, parentIndex)) {
swap(childIndex, parentIndex);
upheapify(parentIndex);
}
}
public static void main(String[] args) {
}
}
Agr min heap bnana ho isse me to, compareTo me isMax boolean variable le lenge










No comments:
Post a Comment