MaxHeap Implementation in java

MaxHeap Implementation in java

  May 30, 2017    

---

As we know maxheap has highest element as root and have smaller elements as children (Separate MaxHeap)
Here i will tell how maxheap can be implemented by Array

Code and Explanation in comments:

import java.util.*;
class maxheap
{
public int heap[];
public static final int front=0;
public int size;
maxheap(int max_size)
{
this.heap[]=new int[max_size];
this.size=-1;
}
int getparent(int n)
{
return n/2;
}
int lchild(int n)
{
return 2*n;
}
int rchild(int n)
{
return 2*n+1;
}
public void swap(int pos1,int pos2)
{
int temp=heap[pos1];
heap[pos1]=heap[pos2];
heap[pos2]=temp;
}

//during insertion we will insert item in array and check whether parent is less than current item if so swap and repeat until item is not less
public void insert(int item)
{
heap[++size]=item;
int temp=size;
while(heap[getparent(temp) < heap[temp] )
{
swap(getparent(temp),size);
temp=getparent(temp);

}

}
//deletion is performed at the root and last node value becomes root and then again it is heapify so that it can hold maxheap property

public int delete(int pos)
{
int data=heap[0];
heap[0]=heap[size--];
heapify(0);
return data;
}
//it will work until node is leaf ,it will check whether the given position is less than child notes if so then swap
public void heapify(int pos)
{
if(leaf(pos))
return;
if(heap[pos]<heap[lchild(pos)])
{
swap(pos,lchild(pos);
heapify(lchild(pos));
}
if(heap[pos]<heap[rchild(pos)])
{
swap(pos,rchild(pos));
heapify(rchild(pos));
}
}
}