With the given pseudocode below, how do I translate them into Java and implement
ID: 3888144 • Letter: W
Question
With the given pseudocode below, how do I translate them into Java and implement them in the following class Heap.java?
2.1 Inserting into a Heap
Algorithm: maxHeapInsert(heap,heapSize, newItem)
{ heap - an array, heapSize - the number of items
in the heap, newItem - the item to be inserted.}
heap[heapSize] <- newitem
place <- heapsize
parent <- (place -1)/2
while parent >= 0 and heap[place] > heap[parent]
swap(heap,place,parent)
place <- parent
parent <- (place - 1)/2
heapSize <- heapSize + 1
________________________________________________
2.2 Deleting from a Heap
Algorithm: maxHeapReheapify(heap,root,heapSize) if root is not a leaf
child <- 2 * root + 1
if root has a right child
if heap[child + 1] > Heap[child])
child <- child + 1
if Heap[root] < Heap[child]
swap(heap,root,child)
MaxHeapReheapify(heap,child,heapSize)
Algorithm: maxHeapDelete(heap)
root <- heap[0]
heap[0] <- heap[heapSize-1]
heapSize <- heapSize - 1
maxHeapReheapify(heap,0,heapSize)
return root
_________________________________________
Heap.java
import java.util.*;
public class Heap> implements HeapAPI
{
/**
* A complete tree stored in an array list representing this
* binary heap
*/
private ArrayList tree;
/**
* Constructs an empty heap
*/
public Heap()
{
}
public boolean isEmpty()
{
if (tree.size() == 0)
{
return true;
}
return false;
}
//Still needs work!
public void insert(E obj)
{
tree.isEmpty;
if (tree.isEmpty)
{
tree.add(obj);
}
else {
tree.add(obj);
int place = tree.size();
int parent = (place -1)/2;
while(parent >= 0 && (tree.get(place) > (tree.get(parent))
{
swap(tree, place, parent)
}
}
place.add();
insert();
}
public E remove() throws HeapException
{
E root = tree.get(0);
tree.set(0 , tree.get(tree.size()-1));
reheapify(0);
return root;
}
public E peek() throws HeapException
{
//implement this method
}
public int size()
{
//implement this method
}
/**
* Swaps a parent and child elements of this heap at the specified indices
* @param place an index of the child element on this heap
* @param parent an index of the parent element on this heap
*/
private void swap(int place, int parent)
{
//implement this method
}
/**
* Rebuilds the heap to ensure that the heap property of the tree is preserved.
* @param root the root index of the subtree to be rebuilt
*/
private void reheapify(int root)
{
if(root =! ){
}
}
}
Explanation / Answer
see below code for Heap Class.
run this code and see the results.
code is fully tested
Code:
import java.util.*;
public class Heap
{
/**
* A complete tree stored in an array list representing this
* binary heap
*/
private ArrayList<Integer> tree;
/**
* Constructs an empty heap
*/
public Heap()
{
tree=new ArrayList<Integer>();
}
public boolean isEmpty()
{
if (tree.size() == 0)
{
return true;
}
return false;
}
//Still needs work!
public void insert(Integer obj)
{
if (isEmpty())
{
tree.add(obj);
}
else
{
tree.add(obj);
int place = tree.size()-1;
int parent = (place -1)/2;
while(parent >= 0 && (tree.get(place) > tree.get(parent)))
{
swap(tree, place, parent);
place=parent;
parent = (place -1)/2;
}
}
}
public Integer remove()
{
Integer root = tree.get(0);
tree.set(0 , tree.get(tree.size()-1));
reheapify(0);
return root;
}
public Integer peek()
{
return tree.get(0);
}
public int size()
{
return tree.size();
}
/**
* Swaps a parent and child elements of this heap at the specified indices
* @param place an index of the child element on this heap
* @param parent an index of the parent element on this heap
*/
private void swap(ArrayList<Integer> tree, int place, int parent)
{
Integer temp=tree.get(place);
tree.add(place, tree.get(parent));
tree.add(parent, temp);
}
/**
* Rebuilds the heap to ensure that the heap property of the tree is preserved.
* @param root the root index of the subtree to be rebuilt
*/
private void reheapify(int root)
{
if (!isLeaf(root))
{
if ( (tree.get(root) < tree.get(leftChild(root))) || (tree.get(root) < tree.get(rightChild(root))))
{
if (tree.get(leftChild(root)) > tree.get(rightChild(root)))
{
swap(tree,root, leftChild(root));
reheapify(leftChild(root));
}else
{
swap(tree,root, rightChild(root));
reheapify(rightChild(root));
}
}
}
}
private int leftChild(int pos)
{
return (2 * pos);
}
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
private boolean isLeaf(int pos)
{
if (pos >= (size() / 2) && pos <= size())
{
return true;
}
return false;
}
}
Mail Method to call this Heap
public class Demo
{
public static void main(String args[])
{
Heap heap=new Heap();
heap.insert(1);
heap.insert(4);
heap.insert(5);
heap.insert(7);
System.out.println(heap.remove());
}
}
Thanks, do rate and provide feedback for my ans. so that i keep working for you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.