I need to write a test method for the heap and ensure that the methods are worki
ID: 3918848 • Letter: I
Question
I need to write a test method for the heap and ensure that the methods are working.
import java.util.NoSuchElementException;
import java.util.Vector;
public class Heap<E extends Comparable<E>> {
private Vector<E> heapArray;
//default constructor
public Heap() {
heapArray= new Vector <E>();
}
/**
@Returns True if heap is empty and false if it is not.
*/
public boolean isEmpty(){
return heapArray.size()==0;
}
/**
@Returns number of items in heap
*/
public int size(){
return heapArray.size();
}
/**
Retrieves, without removing the item in the root.
@returns top item in tree
@throws NoSuchElementExceptionif heap empty
*/
public E getRootItem() throws NoSuchElementException{
if(isEmpty()){
return null;
}
return heapArray.firstElement();
}
/**
Removes the item in the root.
@returns item at root of heap
@throws NoSuchElementException if heap empty
*/
public E removeRootItem() throws NoSuchElementException{
if(isEmpty()){
throw new NoSuchElementException("Heap Empty");
}
int index=0;
return heapArray.remove(index);
}
/**
private int compare(E item1, E item2){
int result=item1.compareTo(item2);
return result;
}
*/
public void insert(E item){
heapArray.add(item);
int index_child=heapArray.size();
int index_parent=(index_child-1)/2;
bubbleUp(index_parent);
}
private int getRightChild(int i){
return 2*i+2;
}
private int getLeftChild(int i){
return 2+i+1;
}
private void bubbleUp(int x) throws IndexOutOfBoundsException{
int place=heapArray.size();
int parent=(place-1)/2;
if ((parent>=0) && (heapArray.get(parent).compareTo(heapArray.get(getLeftChild(place)))<0)){
swap(place,parent);
}else if ((parent>=0) && (heapArray.get(parent).compareTo(heapArray.get(getRightChild(place)))<0)){
swap(place,parent);
}
}
private void swap(int i, int j){
int max=heapArray.size();
if(i<=0 && i>heapArray.size() && j<=0 && j>heapArray.size()){
E temp=heapArray.get(i);
heapArray.set(i,heapArray.get(j));
heapArray.set(j,temp);
}
}
private int kthChild(int i, int k){
return 2*i+k;
}
private int maxChild(int x){
int bestChild = kthChild(x, 1);
int k = 2;
int pos = kthChild(x, k);
while ((k <= 2) && (pos < heapArray.size())){
if (heapArray.get(pos).compareTo(heapArray.get(bestChild)) > 0)
bestChild = pos;
pos = kthChild(x, k++);
}
return bestChild;
}
private void bubbleDown(int x){
int child;
E tmp = heapArray.get(x);
while (kthChild(x, 1) < heapArray.size()){
child = maxChild(x);
if (heapArray.get(child).compareTo(tmp) > 0)
heapArray.set(x, heapArray.get(child));
else
break;
x=child;
}
heapArray.set(x,tmp);
}
public static void main(String[]args){
Heap<Integer> test = new Heap<Integer>();
test.insert(1);
test.insert(2);
test.insert(3);
test.insert(4);
test.insert(5);
test.insert(6);
System.out.println(test.size());
}
}
Explanation / Answer
// the code is really lengthy do you want the test function or do u want me to simplify the code?
// i ll provide you a simple code if you dont like just comment me you want that function only then i will provide that test function for you.
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearranging array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extracting an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// calling max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program(test method for checking all methods)
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
//if you like it give me a thumbs up else just comment how do you want the code.
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearranging array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extracting an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// calling max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program(test method for checking all methods)
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
//if you like it give me a thumbs up else just comment how do you want the code.