Java program to create a Binary Heap and Perform various operation. The followin

Question

Java program to create a Binary Heap and Perform various operation. The following part of program is given . I need full program and method to complete this program.

public class Heap{

public int[] array;

public int count;

public int capacity;

public int heaptype;

public Heap(int capacity,int heaptype)

public parent(int capacity, int heaptype)

public int LeftChild(int i)

public int RightChild(int i)

public int GetMax(int i)

public void PercolateDown()

public int deleteMax()

public int Insert(int data)

public void BuildHeap(heap h,int[]A,int n)

public void HeapSort(int[]A,int n)

I need to further complete these methods. please make sure it is not complex and runs. My grade will be either 0 or 100 depending on it runs or not. please help me out with simpler code that runs. thank you for consideration.

Explanation / Answer

Program:

class BinaryHeap {
  
private int array[];
private int size;
private int capacity;

  
public BinaryHeap(int capacity) {
this.size = 0;
this.capacity = capacity;
this.array = new int[capacity + 1];
}
  
public int size() {
return size;
}
  
public int findMax() {
if (size <= 0) {
throw new RuntimeException("Empty Heap is empty.");
}
return array[1];
}
  
public void insert(int e) {
if (size >= capacity) {
throw new RuntimeException("Heap overflow.");
}
  
size++;
array[size] = e;
percolateUp();
}
  
public int deleteMax() {
if (size <= 0) {
throw new RuntimeException("Empty Heap is empty.");
}
int min = findMax();
array[1] = array[size];
size--;
percolateDown();
return min;
}
  
private void percolateDown() {
int index = 1;
while (true) {
int child = index * 2;
if (child > size)
break;
if (child + 1 <= size) {
// if there are two children -> take the smallest or
// if they are equal take the left one
child = findMax(child, child + 1);
}
if (array[index] <= array[child])
break;
swap(index, child);
index = child;
}
}
  
private void percolateUp() {
int index = size();
while (index > 1) {
int parent = index / 2;
if (array[index] >= array[parent])
break;
swap(index, parent);
index = parent;
}
}
  
private void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
  
private int findMax(int leftChild, int rightChild) {
if (array[leftChild] >= array[rightChild]) {
return leftChild;
} else {
return rightChild;
}
}
/**
* Sorts a given array of items.
*/
public void heapSort(int[] a)
{
  

for (int i = size; i > 0; i--)
{
int tmp = array[i]; //move top item to the end of the heap array
array[i] =array[1];
array[1] = tmp;
size--;
percolateDown();
}
for(int k = 0; k < array.length-1; k++)
array[k] = array[array.length - 1 - k];
}

public static void main(String[] args) {
BinaryHeap bh = new BinaryHeap(10);
bh.insert(7);
bh.insert(5);
bh.insert(9);
bh.insert(6);
bh.insert(4);
bh.insert(8);
bh.insert(10);
bh.insert(1);
bh.insert(3);
bh.insert(2);
  
System.out.println("Size of Binary Heap is : " + bh.size());
  
System.out.println("Delete min from Binary Heap : " + bh.deleteMax());
System.out.println("Size of Binary Heap is : " + bh.size());
  
System.out.println("Delete min from Binary Heap : " + bh.deleteMax());
System.out.println("Size of Binary Heap is : " + bh.size());
}

}

output:

Size of Binary Heap is : 10
Delete min from Binary Heap : 1
Size of Binary Heap is : 9
Delete min from Binary Heap : 6
Size of Binary Heap is : 8

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.