A Way For Learning

Minimum and Maximum element from Max Heap

No comments
Find the minimum and maximum element from given numbers in constant time using Max Heap.
-------------------------------------------------------Program---------------------------------------------------------

public class PriorityQueue {
int[] arr ;
int size;
int max;
    int min;
public PriorityQueue(int arr[]){
size = 0;
max = 1000;
this.arr = arr;
min =99999;
for(int i: arr)
insert(i);
}
public void insert(int e)//E e)
{
if(size==max)
{
System.out.println("full");
}
else
{
arr[size++] = e;
heapify();
if(min>= e)
min=e;
}
}
public void heapify()  //heapfiy from down to up
{
int i = size-1;
int parent =  (i-1)/2;
while(arr[parent]< arr[i])  //heap   max heap
{
int temp = arr[parent];
arr[parent] =arr[i];
arr[i] = temp;
i = parent;   //traversing up
parent = (i-1)/2;
}
}
public void heapify(int index)  //heapfiy from down to up   //HEAPIFY UP
{
int i = index;
int parent =  (i-1)/2;
while(arr[parent]< arr[i])  //heap   max heap
{
int temp = arr[parent];
arr[parent] =arr[i];
arr[i] = temp;
i = parent;   //traversing up
parent = (i-1)/2;
}
}

public void delete_max()
{
int maxele=0;
if(size!=0)
{
maxele = arr[0];
 arr[0] = arr[size-1]; //copy last emelent to front
 if(!(size<=3))
    arr[size-1] =-99999;
 else
 arr[size-1] =-99999;
 size--;  //ignore last element
}
heapifyDown();      // incomplete code
}

public void heapifyDown()  //heapify min heap from root node..after deleteion of root node new lel,ement is root node
{
for(int parent = 0 ; parent< ((size)/2 ) ;parent++) //only parents
{
int right = parent * 2 +2;
int left = parent *2 +1;
if(arr[left]> arr[parent] && (arr[left] >=arr[right] || arr[right]==-9999))
{
int temp = arr[left];
arr[left] = arr[parent];
arr[parent] = temp;
parent = left-1;      // -1 to compensate parent++ in for loop
}
else if(arr[right]> arr[parent] && (arr[left] <= arr[right]  ))
{
int temp = arr[right];
arr[right] = arr[parent];
arr[parent] = temp;
parent = right-1;   // -1 to compensate parent++ in for loop
}
else
break;
}
}

public void heapifyDown(int index)  //heapfiy min heap  from a particular index
{
int tempParent = getParent(index);
for(int parent = tempParent ; parent< (size)/2  ;) //only parents
{
int right = parent * 2 +2;
int left = parent *2 +1;
if(arr[left]> arr[parent] && (arr[left] >=arr[right] || arr[right]==0))
{
int temp = arr[left];
arr[left] = arr[parent];
arr[parent] = temp;
parent = left;
}
else if(arr[right]> arr[parent] && (arr[left] <= arr[right] ))
{
int temp = arr[right];
arr[right] = arr[parent];
arr[parent] = temp;
parent = right;
}
else
break;
}
}
private int getParent(int index)  //get parent index for a child
{
return (index-1)/2;
}
private int right(int index)
{
return (index*2) + 2;
}
private int left(int index)
{
return (index*2) + 1;
}
public boolean isChild(int index)
{
if(index >= ( size/2) +1 )
          return true;
          else
         return false;
}
public void swap(int index1, int index2)
{
 int temp = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = temp;
}

public int extractMaximumElement()
{
int max = 0;
if(size!=0)
{
max = arr[0];
}
return max;
}
public int extractMinimumElement()
{
return min;
}


public void list()
{
for(int i =0 ;i<size;i++)
{
System.out.print(arr[i]);
if(i!=size-1)
{
System.out.print("  ");
}
}
System.out.println("");
}
public void modify(int index, int value)
{
for(int i =0 ;i<size;i++)
{
if(i+1==index)
{
int temp = arr[i];
arr[i]=value;
if(value<temp)
heapifyDown(i);
else if(value>temp)
heapify(i);  //smaller value there for heapify up
break;
}
}

}

}

No comments :

Post a Comment