Question: Part 1: Add the following methods to Heap.java Method T findMin() that returns the key with the smallest priority. For instance, if the heap is
Part 1: Add the following methods to Heap.java
Method T findMin() that returns the key with the smallest priority. For instance, if the heap is
| 90 | 80 | 60 | 20 | 70 | 10 | 15 | 5 | 9 | 50 |
0 1 2 3 4 5 6 7 8 9
the method returns 5. As another example, if the heap is [20, 10, 15, 6, 9, 6], it should return 6. To implement this method, you must not search the entire ArrayList. Rather, you should make use of the heap property and do a smart search. [Hint: the smallest element is always a leaf node].
b) Method T dequeueMin() that returns the key with the smallest priority and also deletes it. You can modify the sifting up operation to do this. For instance, if the heap is:
| 90 | 80 | 60 | 20 | 70 | 10 | 15 | 5 | 9 | 50 |
0 1 2 3 4 5 6 7 8 9
you would first find the smallest priority item using findMin(), then remove the last item (50) and put it in the place of 5.
| 90 | 80 | 60 | 20 | 70 | 10 | 15 | 50 | 9 |
0 1 2 3 4 5 6 7 8
Next sift 50 up until it finds the right spot.
| 90 | 80 | 60 | 50 | 70 | 10 | 15 | 20 | 9 |
0 1 2 3 4 5 6 7 8
If there are multiple keys with the minimum value, T dequeueMin() just removes one item.
Test the two methods in HeapDemo.java.
Heap.java(Add Methods To this class)
import java.util.ArrayList;
public class Heap>
{
ArrayList heapList;
public Heap()
{
heapList = new ArrayList();
}
public int size()
{
return heapList.size();
}
public boolean isEmpty()
{
return heapList.isEmpty();
}
public void clear()
{
heapList.clear();
}
public void enumerate()
{
System.out.println(heapList);
}
public void add(T item)
{
heapList.add(item);
int index = heapList.size()-1;
int pindex = (index-1)/2;
T parent = heapList.get(pindex);
while (index>0 && item.compareTo(parent)>0)
{
heapList.set(index, parent);
heapList.set(pindex, item);
index = pindex;
pindex = (index-1)/2;
parent = heapList.get(pindex);
}
}
public T deleteMax()
{
if (isEmpty())
{
System.out.println("Heap is empty");
return null;
}
else
{
T ret = heapList.get(0); //get the item in the root. This is the largest item.
T item = heapList.remove(heapList.size()-1); //remove the last item.
if (heapList.size()==0)
return ret; //if there was only one item in the heap to begin with, we are done.
heapList.set(0, item); //otherwise, proceed. Put the item in the root.
int index, lIndex, rIndex, maxIndex;
T maxChild;
boolean found=false;
index = 0;
lIndex = index*2+1;
rIndex = index*2+2;
while (!found)
{
if (lIndex
{
//find the maxChild and maxIndex
if (heapList.get(lIndex).compareTo(heapList.get(rIndex))>0)
{
maxChild = heapList.get(lIndex);
maxIndex = lIndex;
}
else
{
maxChild = heapList.get(rIndex);
maxIndex = rIndex;
}
//sift down if necesssary
if (item.compareTo(maxChild)<0)
{
heapList.set(maxIndex, item);
heapList.set(index, maxChild);
index = maxIndex;
}
else
found = true;
}
else if (lIndex < size()) //case 2: item to be sifted down has only left child
//note: item to be sifted down cannot have only right child - it will violate the complete binary tree property
{
if (item.compareTo(heapList.get(lIndex))<0)
{
heapList.set(index, heapList.get(lIndex));
heapList.set(lIndex,item);
index = lIndex;
}
else
found = true;
}
else //case 3: item to be sifted down has no children
found = true;
lIndex = index*2+1;
rIndex = index*2+2;
}
return ret;
}
}
}
///////////////////////////////////////////////////////////////////////////////////
HeapDemo.java(Test Methods Using this class)
import java.util.Scanner;
public class HeapDemo
{
public static void main(String[] args)
{
Heap myHeap = new Heap();
Scanner keyboard = new Scanner(System.in);
System.out.print("Enter positive integers into the heap (-1 when done): ");
Integer num = keyboard.nextInt();
while (num!=-1)
{
myHeap.add(num);
num = keyboard.nextInt();
}
System.out.println("The heap: ");
myHeap.enumerate();
System.out.print("How many nodes to delete (0 to " + myHeap.size() + ")? ");
int d = keyboard.nextInt();
if (d<0||d>myHeap.size())
System.out.println("Can't delete");
else if (d==0)
myHeap.enumerate();
for(int i=1; i<=d;i++){
System.out.println("Deleting " + myHeap.deleteMax());
myHeap.enumerate();
}
}
}
If possible show outputs please and thanks!
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help