In this tutorial we will see all the functionalities of heaps implemented through java language.
Driver program to run:-
package com.problems.heap; public class HeapFunctions { //Function to generate maxheapify where root is max than childs public void maxHeapify(int Arr[],int i,int N) { int largest; int left = 2*i+1; //left child int right = 2*i +2; //right child System.out.println("left"+" "+left); System.out.println("right"+" "+right); System.out.println("Max size"+" "+N); if(left< N && Arr[left] > Arr[i] ) { largest = left; System.out.println("largest left"+largest); } else { largest = i; System.out.println("largest i"+largest); } if(right < N && Arr[right] > Arr[largest] ) { largest = right; System.out.println("largest right"+largest); } if(largest != i ) { System.out.println("No largest"+largest); Arr=swap (Arr, i , largest); maxHeapify (Arr,largest,N); } } //function to generate minheapify where root is minimum than childs public void minHeapify(int Arr[],int i,int N) { int smallest; int left = 2*i+1; //left child int right = 2*i +2; //right child if(left< N && Arr[left]< Arr[i] ) { smallest = left; System.out.println("smallest left"+smallest); } else { smallest = i; System.out.println("smallest i"+smallest); } if(right < N && Arr[right] < Arr[smallest] ) { smallest = right; System.out.println("smallest right"+smallest); } if(smallest != i ) { System.out.println("No largest"+smallest); Arr=swap (Arr, i , smallest); minHeapify (Arr,smallest,N); } } //function to swap elements in an Array public int[] swap(int Arr[],int x,int y) { System.out.println("in swap"); System.out.println("x"+x+"y"+y); int temp=Arr[x]; Arr[x]=Arr[y]; Arr[y]=temp; return Arr; } //function to build maximum heap void build_maxheap (int Arr[ ],int N) { for(int i =N/2; i >= 0 ; i-- ) { maxHeapify (Arr, i,N) ; } } //function to build minimum heap void build_minheap (int Arr[ ],int N) { for(int i =N/2; i >= 0 ; i-- ) { minHeapify (Arr, i,N) ; } } //heap sorting void heap_sort(int Arr[ ],int N) { int heap_size = N; for(int i = N-1; i>=1 ; i-- ) { build_maxheap(Arr,heap_size); System.out.println("this"+i); System.out.println("i="+i+""); Arr=swap(Arr,0, i); heap_size = heap_size-1; System.out.println("calling max heapify"+heap_size); } } }
Driver program to run:-
package com.problems.heap; public class HeapOperations { public static void main(String[] args) { int Elem[]={4,3,7,1,8,5}; HeapFunctions func=new HeapFunctions(); //max heapify func.maxHeapify(Elem, 6, Elem.length); System.out.println("min heap"); func.build_maxheap(Elem, Elem.length); System.out.println(""); for(int i=0;i<Elem.length;i++) { System.out.print(Elem[i]+","); } System.out.println(""); // //min heapify System.out.println("min heap"); func.build_minheap(Elem, Elem.length); System.out.println(""); for(int i=0;i<Elem.length;i++) { System.out.print(Elem[i]+","); } System.out.println(""); // //heap sort System.out.println("Heap Sort length"+ Elem.length); int Elemm[]={4,3,7,1,8,5}; func.heap_sort(Elemm, Elemm.length); System.out.println(""); System.out.println("sorted array"); for(int i=0;i<Elemm.length;i++) { System.out.print(Elemm[i]+","); } // } }
import java.io.BufferedReader;
ReplyDeleteimport java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class heap1 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine().trim());
Heap heap = new Heap(N);
for(int i = 0; i < N; i++){
String[] strings = bufferedReader.readLine().split("\\s+");
int operation = Integer.parseInt(strings[0]);
switch (operation){
case 1: int val = Integer.parseInt(strings[1]);
heap.insert(val);
break;
case 2: int value = Integer.parseInt(strings[1]);
heap.delete(value);
break;
case 3:heap.printMin();
}
}
}
}
class Heap {
int[] array;
int curIndex = 0;
Heap(int N){
array = new int[N];
Arrays.fill(array, Integer.MAX_VALUE);
}
int getParent(int index){
return index/2;
}
int leftChild(int index){
return 2 * index;
}
int rightChild(int index){
return 2*index + 1;
}
boolean isLeaf(int index){
if(index >= (curIndex /2) && index <= curIndex){
return true;
}
return false;
}
void swap(int fromIndex, int toIndex){
int temp = array[fromIndex];
array[fromIndex] = array[toIndex];
array[toIndex] = temp;
}
void insert(int element){
array[++curIndex] = element;
int idx = curIndex;
while (idx > 1 && array[idx] < array[getParent(idx)]){
swap(idx, getParent(idx));
idx = getParent(idx);
}
}
void printMin(){
if(curIndex > 0){
System.out.println(array[1]);
}
}
void heapify(int index){
if(!isLeaf(index)){
int leftChildIndex = leftChild(index);
int rightChildIndex = rightChild(index);
int leftChild = array[leftChildIndex];
int rightChild = array[rightChildIndex];
int item = array[index];
if(leftChild < rightChild){
if(leftChild < item){
swap(leftChildIndex, index);
heapify(leftChildIndex);
}
}
else {
if(rightChild < item) {
swap(rightChildIndex, index);
heapify(rightChildIndex);
}
}
}
}
void delete(int item){
int pos = -1;
for(int i = 1; i <= curIndex; i++){
if(array[i] == item){
pos = i;
break;
}
}
for(int j = pos; j < curIndex; j++){
array[j] = array[j+1];
}
array[curIndex] = Integer.MAX_VALUE;
curIndex--;
if(curIndex > 0)
heapify(1);
}
}