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.

----------------------------------

Do consider following

testHeapOrderEmpty

testHeapOrderSingle

testHeapOrderDoubleGood

testHeapOrderDoubleBad

testHeapOrderTripleGood

testHeapOrderTripleBad

testHeapOrderLargerGood

testHeapOrderLargerBad

testCompleteTreeEmpty

testCompleteTreeSingleGood

testCompleteTreeSingleBad

testCompleteTreeDoubleGood

testCompleteTreeDoubleBad

testCompleteTreeLargerGood

testCompleteTreeLargerBad

--------------------------------

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() {

} }