Program of Heap in Java

A Heap is an extraordinary Tree-based information structure in which the tree is a proper binary tree. By and large, Heaps can be of two kinds:

  1. Max-Heap:  In a Max-Heap the key present at the root hub must be most noteworthy among the keys present at all of it’s youngsters. A similar property must be recursively valid for all sub-trees in that Binary Tree.
  2. Min Heap:   In a Min-Heap the key present at the root hub must be least among the keys present at all of it’s youngsters. A similar property must be recursively valid for all sub-trees in that Binary Tree.

There are three .java classes for theHeap data structure:

  1. Heap.
  2. Node.
  3. Runner

Code is successfully compiled on the Eclipse compiler

Heap:

package heap;

public class Heap {

private Node[] arr;
private int maxSize;
private int currentSize;

public Heap(int max)
{
this.maxSize = max;
currentSize = 0;
arr = new Node[maxSize];
}
public boolean isEmpty()
{
return currentSize == 0;
}
public void insert(int value)
{
Node newNode = new Node(value);
arr[currentSize] = newNode;
trickleUp(currentSize++);
}
public void trickleUp(int index)
{
int parent = (index-1)/2;
Node bottom = arr[index];
while(index > 0 && arr[parent].getKey() < bottom.getKey())
{
arr[index] = arr[parent];
index = parent;
parent = (parent-1)/2;
}
arr[index] = bottom;
}
public Node remove()
{
Node root = arr[0];
arr[0] = arr[currentSize-1];
trickleDown(0);

return root;
}
public void trickleDown(int index)
{
int largerChild;
Node top = arr[index];

while(index < currentSize/2)
{
int leftChild = 2*index +1;
int rightChild = 2*index +2;

if(rightChild < currentSize && arr[leftChild].getKey() < arr[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;

if(top.getKey() >= arr[largerChild].getKey())
break;

arr[index] = arr[largerChild];
index = largerChild;
}
arr[index] = top;
}
public void display()
{
System.out.println(“heapArray:”);

for(int i=0; i<currentSize; i++)
{
if(arr[i] != null)
{
System.out.println(arr[i].getKey() + ” “);
}
else
{
System.out.println(“–“);
}
}
}

}

Node:

package heap;

public class Node {

private int iData;

public Node(int key)
{
iData = key;
}
public int getKey()
{
return this.iData;
}
public void setKey(int id)
{
iData = id;
}
}

Runner:

package heap;

public class Runner {

public static void main(String args[])
{
Heap heap = new Heap(5);

heap.insert(10);
heap.insert(20);
heap.insert(30);
heap.insert(40);
heap.insert(50);

heap.display();
}
}

Add a Comment

Your email address will not be published. Required fields are marked *