In Java language Implement a PQ using the following: - Array Based Tree - Linked
ID: 3763109 • Letter: I
Question
In Java languageImplement a PQ using the following: - Array Based Tree - Linked Structure
Test your implementation by sorting the following pairs using heapSort: (3, "Ahmed"), (9, "Samia"), (6, "Sami"), (7, "Omar" ) , (1, "Khaled" ) , (7, "Abeer" ) , (2, "Fares" ) , (0, "Jaji" ) In Java language
Implement a PQ using the following: - Array Based Tree - Linked Structure
Test your implementation by sorting the following pairs using heapSort: (3, "Ahmed"), (9, "Samia"), (6, "Sami"), (7, "Omar" ) , (1, "Khaled" ) , (7, "Abeer" ) , (2, "Fares" ) , (0, "Jaji" ) In Java language
Implement a PQ using the following: - Array Based Tree - Linked Structure
Test your implementation by sorting the following pairs using heapSort: (3, "Ahmed"), (9, "Samia"), (6, "Sami"), (7, "Omar" ) , (1, "Khaled" ) , (7, "Abeer" ) , (2, "Fares" ) , (0, "Jaji" ) In Java language
Implement a PQ using the following: - Array Based Tree - Linked Structure
Test your implementation by sorting the following pairs using heapSort: (3, "Ahmed"), (9, "Samia"), (6, "Sami"), (7, "Omar" ) , (1, "Khaled" ) , (7, "Abeer" ) , (2, "Fares" ) , (0, "Jaji" )
Explanation / Answer
Answer :
Code for Link List
Code for Node Class
Code for Priority Queue
Using ArrayBased:
public class HeapPriorityQueue implements PriorityQueue
{
public HeapPriorityQueue()
{
items = new ArrayList();
items.add(null);
mySize = 0;
}
public void add(Object x)
{
items.add(x);
mySize++;
int k = mySize;
while (k > 1 && ((Comparable) items.get(k/2)).compareTo(x) > 0) {
items.set(k,items.get(k/2));
k = k/2;
}
items.set(k,x);
}
public Object removeMin()
{
if (! isEmpty()) {
Object min = peekMin();
items.set(1,items.get(mySize));
mySize--;
if (mySize > 1) {
heapify(1);
}
return min;
}
return null;
}
public Object peekMin()
{
return items.get(1);
}
public boolean isEmpty()
{
return mySize == 0;
}
private void heapify(int vroot)
{
Comparable last = (Comparable) items.get(vroot);
int child,k=vroot;
while (2*k <= mySize) {
child = 2*k;
if (child < mySize &&
((Comparable)
items.get(child+1)).compareTo(items.get(child)) < 0) {
child++;
}
if (last.compareTo(items.get(child)) <= 0) {
break;
}
else {
items.set(k,items.get(child));
k = child;
}
}
items.set(k,last);
}
private List items;
private int mySize;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.