Monday, April 18, 2022

Heap Introduction: Max Heap













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

Diagonal Traversal

 eg.  1       2       3       4 5      6       7       8 9    10    11     12 13  14   15    16 Output: 1 6 11 16 2 7 12 3 8 4  Approach:...