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();
}

}

}

Dynamic Programming (Cutting a Rod)

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n.Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

Solution:-

public class Solution {

public static void main(String [] args)

{

int [] price = new int[]{1, 5, 8, 9, 10, 17, 17, 20};

int n = 8 ;

int [] [] dp = new int [n+1][n+1];

for(int i = 1 ; i <= n ; i++){

for(int j = 1 ; j <= n ; j++){

if(i >= j ){

dp[i][j] = Math.max(dp[i][j-1] , dp[i][i - j] + price[j-1]);

}

else{

dp[i][j] = dp[i-1][j];

}

}

}

System.out.println(dp[n][n]);

}

}