Following is a class in which we implemented a priority queue using an array-bas
ID: 3828924 • Letter: F
Question
Following is a class in which we implemented a priority queue using an array-based heap.
Complete the heapOrderValid() and isCompleteTree() methods which verify that the data in store has the specified property.
----------------------------------
---------------------------------
package edu.buffalo.cse116;
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Implementation of a priority queue using an array-based binary tree. This is used to help students understand the
* basic properties binary trees and will have more details explained in future lectures.
*
* @author William J. Collins
* @author Matthew Hertz
* @param Data type (which must be Comparable) of the elements in this tree.
*/
public class PriorityQueue> extends AbstractCollection {
/** Index where the root node can be found. */
private static final int ROOT = 0;
/** Array used to store the elements in the binary tree. */
private E[] store;
/** Number of elements within the tree. */
private int size;
/**
* Initializes this ArrayBinaryTree object to be empty. This creates the array in which items will be stored.
*/
@SuppressWarnings("unchecked")
public PriorityQueue() {
store = (E[]) new Comparable[31];
size = 0;
}
/**
* Checks if the binary tree contains an element at the given index. This requires checking both that the array is
* large enough (to avoid triggering an exception) AND (when the array is large enough) that the array has a non-null
* value at that index.
*
* @param idx Index to be checked out.
* @return True if there is an element at the given index; false otherwise.
*/
private boolean nodeExists(int idx) {
boolean arrayLocationExists = idx < store.length;
return arrayLocationExists && (store[idx] != null);
}
/**
* Given an index, returns the element in that node's left child. If the left child node does not exist, null should
* be returned. It is important that this NOT trigger an index out of bounds exception.
*
* @param idx Index of the node for which we want the left child.
* @return Value of the node's left child or null if no left child exists.
*/
private E leftChild(int idx) {
int leftChild = (idx * 2) + 1;
if (!nodeExists(leftChild)) {
return null;
}
return store[leftChild];
}
/**
* Given an index, returns the element in that node's right child. If the right child node does not exist, null should
* be returned. It is important that this NOT trigger an index out of bounds exception.
*
* @param idx Index of the node for which we want the right child.
* @return Value of the node's right child or null if no right child exists.
*/
private E rightChild(int idx) {
int rightChild = (idx * 2) + 2;
if (!nodeExists(rightChild)) {
return null;
}
return store[rightChild];
}
/**
* Given an index, returns the value of that node's parent. If the node is the root (and so has no parent), null
* should be returned. It is important that this NOT trigger an index out of bounds exception.
*
* @param idx Index of the node for which we want the parent.
* @return Value of the node's parent or null if no parent exists.
*/
private E parent(int idx) {
int parent = (idx - 1) / 2;
if (idx == ROOT) {
return null;
}
return store[parent];
}
/**
* Returns the size of this ArrayBinaryTree object.
*
* @return the size of this ArrayBinaryTree object.
*/
@Override
public int size() {
return size;
}
/**
* Returns an iterator that will return the elements in this ArrayBinaryTree, but without any specific ordering.
*
* @return Iterator positioned at the smallest element in this ArrayBinaryTree object.
*/
@Override
public Iterator iterator() {
// Skipped for now.
throw new UnsupportedOperationException();
}
/**
* Adds the specified element to this heap in the appropriate position according to its key value.
*
* @param obj the element to be added to the heap
* @return Since this method will always succeed, it only returns true.
*/
@Override
public boolean add(E obj) {
// Make certain the store has space to add an element.
if (size == store.length) {
store = Arrays.copyOf(store, store.length * 2);
}
store[size] = obj;
size += 1;
// We will discuss what must happen here so that we guarantee the heap order property on Monday
return true;
}
/**
* Remove the element with the lowest value in this heap and returns a reference to it. Throws an
* NoSuchElementException if the heap is empty.
*
* @return the element with the lowest value in this heap
*/
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException("Cannot call remove on an empty LinkedHeap");
}
E retVal = store[0];
store[0] = store[size - 1];
size -= 1;
// We will discuss what must happen here so that we guarantee the heap order property on Monday
return retVal;
}
/**
* Returns the element with the lowest value in this heap. Throws an NoSuchElementException if the heap is empty.
*
* @return the element with the lowest value in this heap
*/
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("Cannot call remove on an empty LinkedHeap");
}
return store[0];
}
public boolean heapOrderValid() {
}
public boolean isCompleteTree() {
}
}
--------------------------
Test file here
package edu.buffalo.cse116;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.fail;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Random;
import org.junit.Before;
import org.junit.Test;
public class ProperDequeTest {
/** Queue instance used to test some of our code. */
private ProperDeque<Integer> intDeque;
/** Queue instance used to test some of our code. */
private ProperDeque<String> stringDeque;
/** Field definition for ProperDeque#store. This allows us to peek into the internals of the class. */
private Field storeField;
@Before
public void setUp() {
Class<?> properDequeClass = ProperDeque.class;
assertEquals("Your ProperDeque class does not need any additional fields!", 1,
properDequeClass.getDeclaredFields().length);
try {
storeField = properDequeClass.getDeclaredField("store");
} catch (Exception e) {
fail("Your ProperDeque class must preserve the "store" field!");
}
storeField.setAccessible(true);
intDeque = new ProperDeque<>();
stringDeque = new ProperDeque<>();
}
@Test(expected = EmptyDequeException.class)
public void testRemoveFrontWhenEmpty() {
intDeque.removeFront();
}
@Test(expected = EmptyDequeException.class)
public void testRemoveLastWhenEmpty() {
stringDeque.removeLast();
}
@SuppressWarnings("unchecked")
@Test
public void testAddFrontWhenEmpty() throws IllegalArgumentException, IllegalAccessException {
final int ADDED_INTEGER = 45;
intDeque.addFront(ADDED_INTEGER);
ArrayList<Integer> storeList = (ArrayList<Integer>) storeField.get(intDeque);
assertNotNull(""store" field is null after calling addFront()", storeList);
assertEquals("addFront() did not add exactly 1 item to "store"!", 1, storeList.size());
assertEquals("ProperDeque was empty and addFront() did not add it to the 0th entry in "store"", ADDED_INTEGER,
(int) storeList.get(0));
}
@SuppressWarnings("unchecked")
@Test
public void testAddLastWhenEmpty() throws IllegalArgumentException, IllegalAccessException {
final String ADDED_STRING = "This is a test";
stringDeque.addLast(ADDED_STRING);
ArrayList<String> storeList = (ArrayList<String>) storeField.get(stringDeque);
assertNotNull(""store" field is null after calling addLast()", storeList);
assertEquals("addLast() did not add exactly 1 item to "store"!", 1, storeList.size());
assertEquals("ProperDeque was empty and addLast() did not add it to the 0th entry in "store"", ADDED_STRING,
storeList.get(0));
}
@Test
@SuppressWarnings("unchecked")
public void testRemoveFrontWithOneElement() throws IllegalArgumentException, IllegalAccessException {
ArrayList<Object> storeList = (ArrayList<Object>) storeField.get(intDeque);
assertNotNull(""store" field was not instantiated in the constructor", storeList);
final int ADDED_INTEGER = 45;
storeList.add(ADDED_INTEGER);
int iElement = intDeque.removeFront();
assertEquals("ProperDeque contained a single element, but removeFront() did not return it", ADDED_INTEGER,
iElement);
assertNotNull(""store" field is null after calling removeFront()", storeList);
assertEquals("removeFront() did not remove the item from "store"!", 0, storeList.size());
final String ADDED_STRING = "Good testing takes a lot of code to isolate each method.";
storeList = (ArrayList<Object>) storeField.get(stringDeque);
assertNotNull(""store" field was not instantiated in the constructor", storeList);
storeList.add(ADDED_STRING);
String strElement = stringDeque.removeFront();
assertEquals("ProperDeque contained a single element, but removeFront() did not return it", ADDED_STRING,
strElement);
assertNotNull(""store" field is null after calling removeFront()", storeList);
assertEquals("removeFront() did not remove the item from "store"!", 0, storeList.size());
}
@Test
@SuppressWarnings("unchecked")
public void testRemoveLastWithOneElement() throws IllegalArgumentException, IllegalAccessException {
final String ADDED_STRING = "Good testing still takes a lot of code to isolate each method.";
ArrayList<Object> storeList = (ArrayList<Object>) storeField.get(stringDeque);
assertNotNull(""store" field was not instantiated in the constructor", storeList);
storeList.add(ADDED_STRING);
String strElement = stringDeque.removeLast();
assertEquals("ProperDeque contained a single element, but removeLast() did not return it", ADDED_STRING,
strElement);
assertNotNull(""store" field is null after calling removeFront()", storeList);
assertEquals("removeFront() did not remove the item from "store"!", 0, storeList.size());
storeList = (ArrayList<Object>) storeField.get(intDeque);
assertNotNull(""store" field was not instantiated in the constructor", storeList);
final int ADDED_INTEGER = 49;
storeList.add(ADDED_INTEGER);
int iElement = intDeque.removeLast();
assertEquals("ProperDeque contained a single element, but removeLast() did not return it", ADDED_INTEGER,
iElement);
assertNotNull(""store" field is null after calling removeLast()", storeList);
assertEquals("removeFront() did not remove the item from "store"!", 0, storeList.size());
}
@SuppressWarnings("unchecked")
@Test
public void testAddLastWhenNotEmpty() throws IllegalArgumentException, IllegalAccessException {
ArrayList<Integer> storeList = (ArrayList<Integer>) storeField.get(intDeque);
assertNotNull(""store" field is null after the constructor", storeList);
final int[] ADDED_INTEGERS = new int[11];
Random rnd = new Random();
for (int i = 0; i < ADDED_INTEGERS.length; i++ ) {
ADDED_INTEGERS[i] = rnd.nextInt();
storeList.add(ADDED_INTEGERS[i]);
}
final int ADDED_INTEGER = 12;
intDeque.addLast(ADDED_INTEGER);
assertEquals("addLast() did not add exactly 1 item to "store"!", ADDED_INTEGERS.length + 1, storeList.size());
for (int i = 0; i < ADDED_INTEGERS.length; i++ ) {
assertEquals("ProperDeque.addLast() moved the element at index " + i, ADDED_INTEGERS[i], (int) storeList.get(i));
}
assertEquals("ProperDeque.addLast() did not add the element to the end of "store"!", ADDED_INTEGER,
(int) storeList.get(11));
}
@SuppressWarnings("unchecked")
@Test
public void testAddFrontWhenNotEmpty() throws IllegalArgumentException, IllegalAccessException {
ArrayList<String> storeList = (ArrayList<String>) storeField.get(stringDeque);
assertNotNull(""store" field is null after the constructor", storeList);
final String[] ADDED_STRINGS = new String[17];
Random rnd = new Random();
for (int i = 0; i < ADDED_STRINGS.length; i++ ) {
ADDED_STRINGS[i] = Integer.toHexString(rnd.nextInt());
storeList.add(ADDED_STRINGS[i]);
}
final String ADDED_STRING = "This is the real test";
stringDeque.addFront(ADDED_STRING);
assertEquals("addFront() did not add exactly 1 item to "store"!", ADDED_STRINGS.length + 1, storeList.size());
assertEquals("ProperDeque.addFront() did not add the element to the 0th index in "store"!", ADDED_STRING,
storeList.get(0));
for (int i = 0; i < ADDED_STRINGS.length; i++ ) {
assertEquals("ProperDeque.addFront() incorrectly moved the element at index " + i, ADDED_STRINGS[i],
storeList.get(i + 1));
}
}
@SuppressWarnings("unchecked")
@Test
public void testRemoveLastWhenNotEmpty() throws IllegalArgumentException, IllegalAccessException {
ArrayList<Integer> storeList = (ArrayList<Integer>) storeField.get(intDeque);
assertNotNull(""store" field is null after the constructor", storeList);
final int[] ADDED_INTEGERS = new int[8];
Random rnd = new Random();
for (int i = 0; i < ADDED_INTEGERS.length; i++ ) {
ADDED_INTEGERS[i] = rnd.nextInt();
storeList.add(ADDED_INTEGERS[i]);
}
int element = intDeque.removeLast();
assertEquals("removeLast() did not remove exactly 1 item from "store"!", ADDED_INTEGERS.length - 1,
storeList.size());
assertEquals("ProperDeque.removeLast() did not remove the element from the end of "store"!",
ADDED_INTEGERS[ADDED_INTEGERS.length - 1], element);
for (int i = 0; i < (ADDED_INTEGERS.length - 1); i++ ) {
assertEquals("ProperDeque.removeLast() moved the element at index " + i, ADDED_INTEGERS[i],
(int) storeList.get(i));
}
}
@SuppressWarnings("unchecked")
@Test
public void testRemoveFrontWhenNotEmpty() throws IllegalArgumentException, IllegalAccessException {
ArrayList<String> storeList = (ArrayList<String>) storeField.get(stringDeque);
assertNotNull(""store" field is null after the constructor", storeList);
final String[] ADDED_STRINGS = new String[17];
Random rnd = new Random();
for (int i = 0; i < ADDED_STRINGS.length; i++ ) {
ADDED_STRINGS[i] = Integer.toHexString(rnd.nextInt());
storeList.add(ADDED_STRINGS[i]);
}
String element = stringDeque.removeFront();
assertEquals("removeFront() did not remove exactly 1 item from "store"!", ADDED_STRINGS.length - 1,
storeList.size());
assertEquals("ProperDeque.removeFront() did not remove the element from the 0th index of "store"!",
ADDED_STRINGS[0], element);
for (int i = 0; i < (ADDED_STRINGS.length - 1); i++ ) {
assertEquals("ProperDeque.removeFront() incorrectly moved the element at index " + i, ADDED_STRINGS[i + 1],
storeList.get(i));
}
}
}
Explanation / Answer
import java.util.Scanner;
class Task
{
String job;
int priority;
public Task(String job, int priority)
{
this.job = job;
this.priority = priority;
}
public String toString()
{
return "Job Name : "+ job +" Priority : "+ priority;
}
}
class PriorityQueue
{
private Task[] heap;
private int heapSize, capacity;
public PriorityQueue(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
public boolean isEmpty()
{
return heapSize == 0;
}
public boolean isFull()
{
return heapSize == capacity - 1;
}
public int size()
{
return heapSize;
}
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;
}
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;
}
}
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;
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');
}
}