I need help writing a method to subtract - from the priority and time of t.remov
ID: 3768211 • Letter: I
Question
I need help writing a method to subtract - from the priority and time of t.removeMin() and then adding it back to the queue. My main method is below, I just need to write a for loop to help me do this.
import java.security.InvalidKeyException;
import java.util.*;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws PriorityQueueException, InvalidException, InvalidKeyException {
HeapPriorityQueue<Integer,Integer, Integer> t = new
HeapPriorityQueue<Integer,Integer, Integer>();
t.insert(-3, 44, 4);
t.insert(-6, 55, 5);
t.insert(-2, 33, 3);
// Entry e = t.min(); String s = "(" + e.getKey() + ", " + e.getValue() + "," + e.getTime();
// System.out.print(s); System.out.println(t.toString());
while (!t.isEmpty()){
MyPair a = t.removeMin();
System.out.println("add " + a.getValue()+ " with time " + a.getTime()+ " and priority " + a.getKey());
}
import java.security.InvalidKeyException;
import java.util.Comparator;
public class HeapPriorityQueue<K,V, T> {;//implements PriorityQueue<K,V> {
private ArrayListCompleteBinaryTree<K, V, T> heap; // underlying heap
private Comparator<K> comp; // comparator for the keys
//Creates an empty heap with the default comparator
public HeapPriorityQueue() {
heap = new ArrayListCompleteBinaryTree<K, V,T>(); // use an array list
comp = new DefaultComparator<K>(); // use the default comparator
}
//Creates an empty heap with the given comparator
public HeapPriorityQueue(Comparator<K> c) {
heap = new ArrayListCompleteBinaryTree<K, V,T>();
comp = c;
}
public void setComparator(Comparator<K> c) throws IllegalStateException {
if(!isEmpty()) // this only allowed if the priority queue is empty
throw new IllegalStateException("Priority queue is not empty");
comp = c;
}
public int size() { return heap.size(); }
//Returns whether the heap is empty
public boolean isEmpty() { return heap.size() == 0; }
public MyPair min() throws PriorityQueueException, InvalidException {
if (isEmpty())
throw new PriorityQueueException("Priority queue is empty");
return heap.root().getElement();
}
//Inserts a node with key-value pair.
public void insert(K k, V x, T t) throws InvalidKeyException, InvalidException {
checkKey(k); // may throw an InvalidKeyException
MyPair<K, V,T> entry = new MyPair<K, V,T>(k,x,t);
upHeap(heap.add(entry));
}
//Removes and returns an entry with minimum key
public MyPair<K, V,T> removeMin() throws PriorityQueueException, InvalidException {
if (isEmpty())
throw new PriorityQueueException("Priority queue is empty");
MyPair<K, V,T> min = heap.root().getElement();
if (size() == 1)
heap.remove();
else {
heap.replace(heap.root(), heap.remove());
downHeap(heap.root());
}
return min;
}
//Determines whether a given key is valid
private void checkKey(K key) throws InvalidKeyException {
try {
comp.compare(key,key);
}
catch(Exception e) {
throw new InvalidKeyException("Invalid key");
}
}
private void upHeap(Node<K, V,T> v) throws InvalidException {
Node<K, V,T> u;
while (!heap.isRoot(v)) {
u = heap.parent(v);
if (comp.compare(u.getElement().getKey(), v.getElement().getKey()) <= 0) break;
swap(u, v);
v = u;
}
}
//Performs down-heap bubbling
private void downHeap(Node<K,V,T> r) throws InvalidException {
while (heap.isInternal(r)) {
Node<K, V,T> s; // the position of the smaller child
if (!heap.hasRight(r))
s = heap.left(r);
else
if (comp.compare(heap.left(r).getElement().getKey(),
heap.right(r).getElement().getKey()) <=0
)
s = heap.left(r);
else
s = heap.right(r);
if (comp.compare(s.getElement().getKey(), r.getElement().getKey()) < 0) {
swap(r, s);
r = s;
}
else
break;
}
}
//Swaps the pairs of the two given nodes
private void swap(Node<K, V,T> x, Node<K, V,T> y) throws InvalidException {
MyPair<K, V,T> temp = x.getElement();
heap.replace(x, y.getElement());
heap.replace(y, temp);
}
//Text visualization for debugging purposes
public String toString() {
return heap.toString();
}
}
}
}
Explanation / Answer
import java.util.Scanner;
/** class Task **/
class Task
{
String job;
int priority;
/** Constructor **/
public Task(String job, int priority)
{
this.job = job;
this.priority = priority;
}
/** toString() **/
public String toString()
{
return "Job Name : "+ job +" Priority : "+ priority;
}
}
/** Class PriorityQueue **/
class PriorityQueue
{
private Task[] heap;
private int heapSize, capacity;
/** Constructor **/
public PriorityQueue(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
/** function to clear **/
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
/** function to check if empty **/
public boolean isEmpty()
{
return heapSize == 0;
}
/** function to check if full **/
public boolean isFull()
{
return heapSize == capacity - 1;
}
/** function to get Size **/
public int size()
{
return heapSize;
}
/** function to insert task **/
public void insert(String job, int priority)
{
Task newJob = new Task(job, priority);
heap[++heapSize] = newJob;
int pos = heapSize;
while (pos != 1 && newJob.priority > heap[pos/2].priority)
{
heap[pos] = heap[pos/2];
pos /=2;
}
heap[pos] = newJob;
}
/** function to remove task **/
public Task remove()
{
int parent, child;
Task item, temp;
if (isEmpty() )
{
System.out.println("Heap is empty");
return null;
}
item = heap[1];
temp = heap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heap[child].priority < heap[child + 1].priority)
child++;
if (temp.priority >= heap[child].priority)
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
}
/** Class PriorityQueueTest **/
public class PriorityQueueTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Priority Queue Test ");
System.out.println("Enter size of priority queue ");
PriorityQueue pq = new PriorityQueue(scan.nextInt() );
char ch;
/* Perform Priority Queue operations */
do
{
System.out.println(" Priority Queue Operations ");
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. check empty");
System.out.println("4. check full");
System.out.println("5. clear");
System.out.println("6. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter job name and priority");
pq.insert(scan.next(), scan.nextInt() );
break;
case 2 :
System.out.println(" Job removed "+ pq.remove());
break;
case 3 :
System.out.println(" Empty Status : "+ pq.isEmpty() );
break;
case 4 :
System.out.println(" Full Status : "+ pq.isFull() );
break;
case 5 :
System.out.println(" Priority Queue Cleared");
pq.clear();
break;
case 6 :
System.out.println(" Size = "+ pq.size() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}