Minimum and Maximum element from Max Heap
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;
}
}
}
}
-------------------------------------------------------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;
}
}
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment