I am not passing some of the code when i run the testing . PriorityQueue public...
I am not passing some of the code when i run the testing .
PriorityQueue
public class PriorityQueue<T extends Comparable<T>>
implements IPriorityQueue<T> {
private Vector<T> theVector = new
Vector<>(0, 1);
private int size = 0;
@Override
public void insert(T element) {
theVector.pushBack(element);
size++;
bubbleUp();
}
@Override
public T peekTop() throws
java.util.NoSuchElementException {
if (isEmpty()) {
throw new
java.util.NoSuchElementException();
}
return theVector.get(0);
}
@Override
public T getTop() throws
java.util.NoSuchElementException {
T top = null;
if (isEmpty()) {
throw new
java.util.NoSuchElementException();
}
top = theVector.get(0);
theVector.set(0, null);
size--;
if (!isEmpty()) {
theVector.set(0,
theVector.get(size));
}
theVector.popBack();
bubbleDown();
return top;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
private void bubbleUp() {
}
private void bubbleDown() {
}
private boolean isRoot(int index) {
return index == 0;
}
private boolean isLeaf(int index) {
int leftIndex =
getLeftChildIndex(index);
int rightIndex =
getRightChildIndex(index);
return leftIndex >= size
&& rightIndex >= size;
}
private T getValue(int index) {
return theVector.get(index);
}
private T getParentValue(int index) throws
java.lang.IllegalArgumentException {
if (isRoot(index)) {
throw new
IllegalArgumentException();
}
return
theVector.get(getParentIndex(index));
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private int getLeftChildIndex(int index) {
return index * 2 + 1;
}
private int getRightChildIndex(int index) {
return index * 2 + 2;
}
@SuppressWarnings("unused")
private int getMinimumChildIndex(int index) {
int leftIndex =
getLeftChildIndex(index);
T leftValue =
getValue(leftIndex);
int rightIndex =
getRightChildIndex(index);
int minChildIndex =
leftIndex;
if (rightIndex <
theVector.getSize()) {
T rightValue =
getValue(rightIndex);
if (rightValue
!= null && leftValue.compareTo(rightValue) > 0) {
minChildIndex = rightIndex;
}
}
return minChildIndex;
}
@Override
public String toString() {
String s =
theVector.toString();
return
s.substring(s.indexOf("["));
}
boolean isHeap() {
boolean b = true;
for (int i = 0; b && i <
size; i++) {
int index =
i;
if
(getValue(index) == null) {
b = false;
break;
}
if
(isLeaf(index)) {
while (!isRoot(index)) {
T parentValue =
getParentValue(index);
T value =
getValue(index);
if
(value.compareTo(parentValue) >= 0) {
index =
getParentIndex(index);
} else {
b =
false;
break;
}
}
}
}
return b;
}
}
PriorityQueueTests
@Test
public void insertTwoItemsInReverseOrder() {
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(40);
thePQ.insert(30);
thePQ.insert(20);
thePQ.insert(10);
assertEquals(10,
thePQ.peekTop().intValue());
assertTrue(thePQ.isHeap());
}
@Test
public void
insertTenItemsPQSizeReverseOrderIsCorrect() {
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(100);
thePQ.insert(90);
thePQ.insert(80);
thePQ.insert(70);
thePQ.insert(60);
thePQ.insert(50);
thePQ.insert(40);
thePQ.insert(30);
thePQ.insert(20);
thePQ.insert(10);
assertFalse(thePQ.isEmpty());
assertEquals(10,
thePQ.getSize());
assertTrue(thePQ.isHeap());
}
@Test
public void insertTwoItemGetTopOnePQSizeIsCorrect()
{
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(20);
thePQ.insert(10);
thePQ.insert(30);
thePQ.getTop();
assertFalse(thePQ.isEmpty());
assertEquals(2,
thePQ.getSize());
assertTrue(thePQ.isHeap());
}
@Test
public void testDoubleBubbleDown() {
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(2);
thePQ.insert(3);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(6);
thePQ.insert(7);
thePQ.insert(8);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
}
@Test
public void testRightRightSwap() {
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(3);
thePQ.insert(2);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(7);
thePQ.insert(6);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(2, i);
assertTrue(thePQ.isHeap());
}
@Test
public void testRightLeftSwap() {
PriorityQueue<Integer> thePQ
= new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(3);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(2);
thePQ.insert(7);
thePQ.insert(6);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(2, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(3, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(4, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(5, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(6, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(7, i);
assertTrue(thePQ.isHeap());
assertTrue(thePQ.isEmpty());
}
Testing: PriorityQueueTests
FAILURE: insertTwoItemsInReverseOrder
FAILURE: testRightLeftSwap
Success: insertOneItemGetTopOnePQSizeIsCorrect
Success: insertTwoItemsPQSizeIsCorrect
FAILURE: insertTwoItemGetTopOnePQSizeIsCorrect
Success: testRightSwap
FAILURE: testDoubleBubbleDown
Success: insertItemPQSizeIsCorrect
FAILURE: insertTenItemsPQSizeReverseOrderIsCorrect
Success: insertTenItemsPQSizeIsCorrect
Success: insertTwoItemGetTopTwoPQSizeIsCorrect
Success: newPQisEmpty
FAILURE: testRightRightSwap
Homework Answers
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.Vector;
import org.junit.Test;
class PriorityQueue<T extends Comparable<T>> {
private Vector<T> theVector = new Vector<>(0, 1);
private int size = 0;
public void insert(T element) {
theVector.addElement(element);
size++;
bubbleUp();
}
public T peekTop() throws java.util.NoSuchElementException {
if (isEmpty()) {
throw new java.util.NoSuchElementException();
}
return theVector.get(0);
}
public T getTop() throws java.util.NoSuchElementException {
T top = null;
if (isEmpty()) {
throw new java.util.NoSuchElementException();
}
top = theVector.get(0);
theVector.set(0, null);
size--;
if (!isEmpty()) {
theVector.set(0, theVector.get(size));
}
theVector.remove(theVector.size() - 1);
bubbleDown();
return top;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void bubbleUp() {
int index = theVector.size() - 1;
while ((index != 0) && (getParentValue(index).compareTo(theVector.get(index)) > 0)) {
// If parent/child are out of order; swap them
swap(index, getParentIndex(index));
// in next iteration proceed with checking parent node
// we will keep doing this till we reach root of tree
index = getParentIndex(index);
}
}
private void swap(int index1, int index2) {
T tmp = theVector.get(index1);
theVector.set(index1, theVector.get(index2));
theVector.set(index2, tmp);
}
private void bubbleDown() {
int index = 0;
while(!isLeaf(index)) {
int childIndex = getMinimumChildIndex(index);
if(childIndex < theVector.size()) {
if(theVector.get(childIndex).compareTo(theVector.get(index)) < 0) {
swap(index, childIndex);
}
index = childIndex;
} else {
break;
}
}
}
private boolean isRoot(int index) {
return index == 0;
}
private boolean isLeaf(int index) {
int leftIndex = getLeftChildIndex(index);
int rightIndex = getRightChildIndex(index);
return leftIndex >= size && rightIndex >= size;
}
private T getValue(int index) {
return theVector.get(index);
}
private T getParentValue(int index) throws java.lang.IllegalArgumentException {
if (isRoot(index)) {
throw new IllegalArgumentException();
}
return theVector.get(getParentIndex(index));
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private int getLeftChildIndex(int index) {
return index * 2 + 1;
}
private int getRightChildIndex(int index) {
return index * 2 + 2;
}
@SuppressWarnings("unused")
private int getMinimumChildIndex(int index) {
int leftIndex = getLeftChildIndex(index);
T leftValue = getValue(leftIndex);
int rightIndex = getRightChildIndex(index);
int minChildIndex = leftIndex;
if (rightIndex < theVector.size()) {
T rightValue = getValue(rightIndex);
if (rightValue != null && leftValue.compareTo(rightValue) > 0) {
minChildIndex = rightIndex;
}
}
return minChildIndex;
}
@Override
public String toString() {
String s = theVector.toString();
return s.substring(s.indexOf("["));
}
boolean isHeap() {
boolean b = true;
for (int i = 0; b && i < size; i++) {
int index = i;
if (getValue(index) == null) {
b = false;
break;
}
if (isLeaf(index)) {
while (!isRoot(index)) {
T parentValue = getParentValue(index);
T value = getValue(index);
if (value.compareTo(parentValue) >= 0) {
index = getParentIndex(index);
} else {
b = false;
break;
}
}
}
}
return b;
}
}
public class PriorityQueueTests {
@Test
public void insertTwoItemsInReverseOrder() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(40);
thePQ.insert(30);
thePQ.insert(20);
thePQ.insert(10);
assertEquals(10, thePQ.peekTop().intValue());
assertTrue(thePQ.isHeap());
}
@Test
public void insertTenItemsPQSizeReverseOrderIsCorrect() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(100);
thePQ.insert(90);
thePQ.insert(80);
thePQ.insert(70);
thePQ.insert(60);
thePQ.insert(50);
thePQ.insert(40);
thePQ.insert(30);
thePQ.insert(20);
thePQ.insert(10);
assertFalse(thePQ.isEmpty());
assertEquals(10, thePQ.getSize());
assertTrue(thePQ.isHeap());
}
@Test
public void insertTwoItemGetTopOnePQSizeIsCorrect() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(20);
thePQ.insert(10);
thePQ.insert(30);
thePQ.getTop();
assertFalse(thePQ.isEmpty());
assertEquals(2, thePQ.getSize());
assertTrue(thePQ.isHeap());
}
@Test
public void testDoubleBubbleDown() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(2);
thePQ.insert(3);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(6);
thePQ.insert(7);
thePQ.insert(8);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
}
@Test
public void testRightRightSwap() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(3);
thePQ.insert(2);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(7);
thePQ.insert(6);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(2, i);
assertTrue(thePQ.isHeap());
}
@org.junit.Test
public void testRightLeftSwap() {
PriorityQueue<Integer> thePQ = new PriorityQueue<>();
thePQ.insert(1);
thePQ.insert(3);
thePQ.insert(4);
thePQ.insert(5);
thePQ.insert(2);
thePQ.insert(7);
thePQ.insert(6);
assertTrue(thePQ.isHeap());
int i = thePQ.getTop();
assertEquals(1, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(2, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(3, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(4, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(5, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(6, i);
assertTrue(thePQ.isHeap());
i = thePQ.getTop();
assertEquals(7, i);
assertTrue(thePQ.isHeap());
assertTrue(thePQ.isEmpty());
}
}
You did not implement the heapify up and down method, due to which this errors were coming.. As you have not provided your vector classes, i am using java.util.vector and doing the operation.. you can similarly replace it with your class method if you want.. Please upvote for the effort i have taken to resolve this. Thanks!
Add Answer to:
I am not passing some of the code when i run the testing .
PriorityQueue
public...
I need some help with some homework questions. How would I implement the to-do's? ----------------------------------------------------------------------------------------------------------------------------------------------------------- AbstractArrayHea
I need some help with some homework questions. How would I implement the to-do's? ----------------------------------------------------------------------------------------------------------------------------------------------------------- AbstractArrayHeap.Java package structures; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.NoSuchElementException; public abstract class AbstractArrayHeap<P, V> { protected final ArrayList<Entry<P, V>> heap; protected final Comparator<P> comparator; protected AbstractArrayHeap(Comparator<P> comparator) { if (comparator == null) { throw new NullPointerException(); } this.comparator = comparator; heap = new ArrayList<Entry<P, V>>(); } public final AbstractArrayHeap<P, V> add(P priority, V value) { if (priority == null || value...
I need help with todo line please public class LinkedList { private Node head; public LinkedList()...
I need help with todo line please public class LinkedList { private Node head; public LinkedList() { head = null; } public boolean isEmpty() { return head == null; } public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.getNext(); } return count; } public void add(int data) { Node newNode = new Node(data); newNode.setNext(head); head = newNode; } public void append(int data) { Node newNode = new Node(data);...
What is wrong with my code, when I pass in 4 It will not run, without...
What is wrong with my code, when I pass in 4 It will not run, without the 4 it will run, but throw and error. I am getting the error required: no arguments found: int reason: actual and formal argument lists differ in length where T is a type-variable: T extends Object declared in class LinkedDropOutStack public class Help { /** * Program entry point for drop-out stack testing. * @param args Argument list. */ public static void main(String[] args)...
This wont take you more than 15 mins. Comple the two method and besure to test...
This wont take you more than 15 mins. Comple the two method and besure to test with Junit test that provided below. toArray() -- this method returns a newly allocated array containing the elements in the multiset. The array this method returns must only contain the elements in the multiset and not any nulls or other values that are stored in the backing store, but are not in the multiset. fromArray(E[] arr) -- this method updates the multiset so that...
Can Anyone help me to convert Below code to C++! Thanks For example, in C++, the...
Can Anyone help me to convert Below code to C++! Thanks For example, in C++, the function headers would be the following: class MaxHeap { vector<int> data; public: MaxHeap() { // ... } int size() { // ... } int maxLookup() { // ... } void extractMax() { // ... } void insert(int data) { // ... } void remove(int index) { // ... } }; ======================== import java.util.Arrays; import java.util.Scanner; public class MaxHeap { Integer[] a; int size; //...
Implement the missing methods in java! Thanks! import java.util.Iterator; import java.util.NoSuchElementException; public class HashTableOpenAddressing<K, V> implements...
Implement the missing methods in java! Thanks! import java.util.Iterator; import java.util.NoSuchElementException; public class HashTableOpenAddressing<K, V> implements DictionaryInterface<K, V> { private int numEntries; private static final int DEFAULT_CAPACITY = 5; private static final int MAX_CAPACITY = 10000; private TableEntry<K, V>[] table; private double loadFactor; private static final double DEFAULT_LOAD_FACTOR = 0.75; public HashTableOpenAddressing() { this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashTableOpenAddressing(int initialCapacity, double loadFactorIn) { numEntries = 0; if (loadFactorIn <= 0 || initialCapacity <= 0) { throw new IllegalArgumentException("Initial capacity and load...
import java.util.Scanner; import class17.HeapPriorityQueue; import class17.PriorityQueue; /*************** * Homework D * * * Remove any initial...
import java.util.Scanner; import class17.HeapPriorityQueue; import class17.PriorityQueue; /*************** * Homework D * * * Remove any initial package declaration that might be added to your file in * case you edit it in eclipse. * * The goal of the homework is to create two ArrayList based implementations of * a Priority Queue as explained in Section 9.2 (in 9.2.4 and 9.2.5) of the * textbook. * * These are to be made by completing the classes PQunsorted and PQsorted as...
I need help fixing my java code for some reason it will not let me run...
I need help fixing my java code for some reason it will not let me run it can someone pls help me fix it. class LinearProbingHashTable1 { private int keyname; private int valuename; LinearProbingHashTable1(int keyname, int valuename) { this.keyname = keyname; this.valuename = valuename; } public int getKey() { return keyname; } public int getValue() { return valuename; } } class LinearProbingHashTable2 { private final static int SIZE = 128; LinearProbingHashTable2[] table; LinearProbingHashTable2() { table = new LinearProbingHashTable2[SIZE]; for (int...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to both classes: public void reverseThisList(), This method will reverse the lists. When testing the method: print out the original list, call the new method, then print out the list again ------------------------------------------------------------------------- //ARRAY LIST class: public class ArrayList<E> implements List<E> { /** Array of elements in this List. */ private E[] data; /** Number of elements currently in this List. */ private int size; /**...
In Java, you'll find that it contains several methods that have not yet been finished. For now, the methods contain...
In Java, you'll find that it contains several methods that have not yet been finished. For now, the methods contain only a placeholder return value so that the code will compile. Fill in your own implementation. public class SomePracticeStringMethods { /* * returns true if c is a letter in the word "temple" or false otherwise */ public static boolean inTU(char c) { /* placeholder just so that the function * compiles. fill in your implementation here. * * there...
Most questions answered within 3 hours.
-
#22 Suppose cars pass an intersection at a rate of 120 per hour.
What is the...
asked 59 minutes ago -
for project management course
An indicator of project success within an organization is the
strength of...
asked 1 hour ago -
How did immigration affect the culture of the United States?
Explain in detail and give specific...
asked 1 hour ago -
A dolphin in an aquatic show jumps straight up out of the water
at a velocity...
asked 2 hours ago -
x
P(x)
0
0.25
1
0.2
2
0.15
3
0.4
Find the standard deviation of this...
asked 3 hours ago -
An economist claims that he has found evidence to support the
assumption that the investment expenditure...
asked 4 hours ago -
Question 10 (1 point)
Suppose that a researcher studying the weight of female college
athletes wants...
asked 5 hours ago -
a. Using your
molecular modeling kit, build a model of sucrose. Locate the oxygen
bridge in...
asked 5 hours ago -
Below is a
linear time complexity algorithm Max-Min-VER1 to find the biggest
and smallest element a...
asked 5 hours ago -
A women tries to swim perpendicular across the river to the
opposite bank at 2.0m/s with...
asked 6 hours ago -
The amount of time it takes for a student to complete a
statistics quiz is uniformly...
asked 7 hours ago -
True or False: If some system undergoes a reversible,
isothermal
process, then its entropy must remain...
asked 6 hours ago