Heap Data Structure Implementation in Java

Here is the Implementation of Maximum Heap in Java.Although best approach is to implement Object oriented approach during developing Classes.


import java.util.Scanner;


class Heap{
public int [] array; // containing the heap

public int capacity ;

public int count ; //num of element in a heap


public Heap(int capacity){
this.capacity = capacity;
this.array = new int[capacity];

}

public int parent(int i){
return i - 1 / 2 ;

}

public int left(int i){
int left = 2 * i + 1;

if(left >= this.count || i < 0){
return -1;
}

return left;
}

public int right(int i){

int right = 2 * i + 2;

if(right >= this.count || i < 0){
return -1;
}
return right ;
}

public int getMaximum(){
if(this.count == 0 ){
return -1;
}
else{
return this.array[0];
}
}

public void percolateDown(int i){

int l = left(i);
int r = right(i);
int max = 0 ;
if(l != -1 && this.array[i] < this.array[l]){
max = l;
}
else{
max = i ;
}
if(r != -1 && this.array[i] > this.array[max]){
max = r;
}


if(max != i){
int temp  = this.array[max];
this.array[max] = this.array[i];
this.array[i] = temp;
percolateDown(max);
}

}

public int deleteMax(){
if(this.count == 0){
return -1;
}
int data = this.array[0];
this.array[0] = this.array[this.count -1 ];
this.count--;
percolateDown(0);

return data;
}

public void insert(int data){
if(this.count == this.capacity){
System.out.println("Heap is Full");
}
else{
this.count++;
int i = this.count - 1 ;
while(i > 0 && this.array[(i-1)/2] < data){
this.array[i] = this.array[(i-1)/2];
i = (i - 1) / 2 ;
}
this.array[i] = data;
}
}


}





public class Solution {

public static void main(String [] args)
{
System.out.println("heap");

Heap heap = new Heap(8);
heap.insert(1);
heap.insert(13);
heap.insert(6);
heap.insert(17);
heap.insert(4);
heap.insert(2);
heap.insert(5);


for(int i = 0 ; i < 8 ; i++){
System.out.println("max is " +heap.getMaximum());
System.out.println("left is "+ heap.left(i)+" right "+ heap.right(i));
if(heap.left(i) != -1){
System.out.println("data left "+ heap.array[heap.left(i)]);
}
if(heap.right(i) != -1){
System.out.println("data right "+ heap.array[heap.right(i)]);
}
heap.deleteMax();
}

}

}