Question

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 == null) {

      throw new NullPointerException("priority and value must be non-null.");

    }

    Entry<P, V> entry = new Entry<P, V>(priority, value);

    heap.add(entry);

    bubbleUp(heap.size() - 1);

    return this;

  }

public final V peek() {

    if (heap.isEmpty()) {

      throw new NoSuchElementException("Cannot peek at an empty ArrayHeap.");

    }

    return heap.get(0).getValue();

  }

public final V remove() {

    if (heap.isEmpty()) {

      throw new IllegalStateException("Cannot remove from an empty ArrayHeap.");

    }

    swap(0, heap.size() - 1);

    V val = heap.remove(heap.size() - 1).getValue();

    if (!heap.isEmpty()) {

      bubbleDown(0);

    }

    return val;

  }

public final int size() {

    return heap.size();

  }

public final boolean isEmpty() {

    return heap.isEmpty();

  }

public final List<Entry<P, V>> asList() {

    return Collections.unmodifiableList(heap);

  }

public final Comparator<P> getComparator() {

    return this.comparator;

  }

public final void swap(int ix0, int ix1) {

    if (ix0 < 0 || ix0 >= heap.size() || ix1 < 0 || ix1 >= heap.size())

      throw new IndexOutOfBoundsException();

    Entry<P, V> e0 = heap.get(ix0);

    Entry<P, V> e1 = heap.get(ix1);

    heap.set(ix0, e1);

    heap.set(ix1, e0);

  }

  public abstract int getLeftChildOf(int index);

  public abstract int getRightChildOf(int index);

  public abstract int getParentOf(int index);

  protected abstract void bubbleUp(int index);

  protected abstract void bubbleDown(int index);

}

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

StudentArrayHeap.Java

package structures;

import java.util.Comparator;

import java.util.Iterator;

public class StudentArrayHeap<P, V> extends AbstractArrayHeap<P, V> {

  // TODO: Implement all abstract methods from AbstractArrayHeap.

}

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

PriorityQueue.Java

package structures;

import java.util.Comparator;

import java.util.Iterator;

public interface PriorityQueue<P, V> extends Iterable<Entry<P, V>> {

  public PriorityQueue<P, V> enqueue(P priority, V value);

  public V dequeue();

  public V peek();

  public Iterator<Entry<P, V>> iterator();

  public Comparator<P> getComparator();

  public int size();

  public boolean isEmpty();

}

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

MinQueue.Java

package structures;

import comparators.ReverseIntegerComparator;

import java.util.Comparator;

import java.util.Iterator;

public class MinQueue<V> implements PriorityQueue<Integer, V> {

  // TODO: Implement all abstract methods from PriorityQueue.

}

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

MaxQueue.Java

package structures;

import comparators.IntegerComparator;

import java.util.Comparator;

import java.util.Iterator;

public class MaxQueue<V> implements PriorityQueue<Integer, V> {

  // TODO: Implement all abstract methods from PriorityQueue.

}

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

StringLengthComparator.Java

package comparators;

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {

  @Override

  public int compare(String arg0, String arg1) {

    if (arg0.length() < arg1.length()) return -1;

    if (arg0.length() > arg1.length()) return 1;

    return arg0.compareTo(arg1);

  }

}

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

IntegerComparator.java

package comparators;

import java.util.Comparator;

public class IntegerComparator implements Comparator<Integer> {

  @Override

  public int compare(Integer arg0, Integer arg1) {

    // TODO: Implement the compare() method

    return 0;

  }

}

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

ReverseIntegerComparator.java

package comparators;

import java.util.Comparator;

public class ReverseIntegerComparator implements Comparator<Integer> {

  @Override

  public int compare(Integer arg0, Integer arg1) {

    // TODO: Implement the compare() method

    return 0;

  }

}

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

Entry.Java

package structures;

public final class Entry<P, V> {

  private final P priority;

  private final V value;

public Entry(P priority, V value) {

    if (priority == null || value == null) {

      throw new NullPointerException("The priority and value must be non-null.");

    }

    this.priority = priority;

    this.value = value;

  }

public final P getPriority() {

    return priority;

  }

public final V getValue() {

    return value;

  }

}

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

Thanks for the help!

Answer 1

Working code implemented in Java and appropriate comments provided for better understanding:

Here I am attaching code for these files:

• AbstractArrayHeap.Java
• StudentArrayHeap.Java
• PriorityQueue.Java
• MinQueue.Java
• MaxQueue.Java
• StringLengthComparator.Java
• IntegerComparator.java
• ReverseIntegerComparator.java
• Entry.java

Source code for AbstractArrayHeap.Java:

package structures;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;

/**
* An {@link AbstractArrayHeap} is an implementation of a heap that represents
* the tree using an array. By doing this, we can easily maintain the complete
* tree property required by a Heap.
*
* @param <P> - the type of the priority values
* @param <V> - the type of the associated values
* @see http://en.wikipedia.org/wiki/Heap_(data_structure)
*/
public abstract class AbstractArrayHeap<P, V> {

/**
* The array representation of our heap
*/
protected final ArrayList<Entry<P, V>> heap;

/**
* The {@link Comparator} which determines priorities in this
* {@link AbstractArrayHeap}.
*/
protected final Comparator<P> comparator;

/**
* Creates an {@link AbstractArrayHeap} with the specified
* {@link Comparator} for determining priority
*
* @param comparator
* the {@link Comparator} to use to determine priority
* @throws NullPointerException
* if {@code comparator} is {@code null}
*/
protected AbstractArrayHeap(Comparator<P> comparator) {
if (comparator == null) {
throw new NullPointerException();
}
this.comparator = comparator;
heap = new ArrayList<Entry<P, V>>();
}

/**
* Adds the specified {@code value} to this {@link AbstractArrayHeap} with
* the specified {@code priority}. For convenience, returns the modified
* {@link AbstractArrayHeap}.
*
* @param priority
* the priority for this entry
* @param value
* the value for this entry
* @return The modified {@link AbstractArrayHeap}
* @throws NullPointerException
* if {@code priority} or {@code value} are {@code null}.
*/
public final AbstractArrayHeap<P, V> add(P priority, V value) {
if (priority == null || value == null) {
throw new NullPointerException("priority and value must be non-null.");
}
Entry<P, V> entry = new Entry<P, V>(priority, value);
heap.add(entry);
bubbleUp(heap.size() - 1);
return this;
}

/**
* Returns the value that has the highest priority as determined by
* {@link AbstractArrayHeap#getComparator()}.
*
* @return the value that has the highest priority
* @throws NoSuchElementException
* if this {@link AbstractArrayHeap} is empty
*/
public final V peek() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Cannot peek at an empty ArrayHeap.");
}
return heap.get(0).getValue();
}

/**
* Removes the value that has the highest priority as determined by
* {@link AbstractArrayHeap#getComparator()} from this
* {@link AbstractArrayHeap}. For convenience, this method returns the
* removed value.
*
* @return the removed value
*/
public final V remove() {
if (heap.isEmpty()) {
throw new IllegalStateException("Cannot remove from an empty ArrayHeap.");
}
swap(0, heap.size() - 1);
V val = heap.remove(heap.size() - 1).getValue();

if (!heap.isEmpty()) {
bubbleDown(0);
}
  
return val;
}

/**
* Returns the number of elements in this {@link AbstractArrayHeap}.
*
* @return the number of elements in this {@link AbstractArrayHeap}.
*/
public final int size() {
return heap.size();
}

/**
* Returns {@code true} if this {@link AbstractArrayHeap} has no elements in
* it and {@code false} otherwise.
*
* @return {@code true} if this {@link AbstractArrayHeap} has no elements in
* it and {@code false} otherwise.
*/
public final boolean isEmpty() {
return heap.isEmpty();
}

/**
* Returns an immutable view of the underlying array structure of this
* {@link AbstractArrayHeap}.
*
* @return an immutable view of the underlying array structure of this
* {@link AbstractArrayHeap}.
*/
public final List<Entry<P, V>> asList() {
return Collections.unmodifiableList(heap);
}

/**
* Returns the {@link Comparator} that is used to determine priority in this
* {@link AbstractArrayHeap}.
*
* @return the {@link Comparator} that is used to determine priority in this
* {@link AbstractArrayHeap}.
*/
public final Comparator<P> getComparator() {
return this.comparator;
}

/**
* Given two indices, swaps the values of those two indices.
*
* @param ix0
* the first index
* @param ix1
* the second index
* @throws IndexOutOfBoundsException
* if either index is less than 0 or greater than or equal to
* the size of this {@link AbstractArrayHeap}
*/
protected final void swap(int ix0, int ix1) {
if (ix0 < 0 || ix0 >= heap.size() || ix1 < 0 || ix1 >= heap.size())
throw new IndexOutOfBoundsException();
Entry<P, V> e0 = heap.get(ix0);
Entry<P, V> e1 = heap.get(ix1);
heap.set(ix0, e1);
heap.set(ix1, e0);
}

/**
* Given an index of some "node" returns the index to that "nodes" left
* child.
*
* @param index
* an index in this {@link AbstractArrayHeap}
* @return the index of the specified "nodes" left child
* @throws IndexOutOfBoundsException
* if {@code index} is less than 0
*/
protected abstract int getLeftChildOf(int index);

/**
* Given an index of some "node" returns the index to that "nodes" right
* child.
*
* @param index
* a "nodes" index
* @return the index of the specified "nodes" right child
* @throws IndexOutOfBoundsException
* if {@code index} is less than 0
*/
protected abstract int getRightChildOf(int index);

/**
* Given an index of some "node" returns the index to that "nodes" parent.
*
* @param index
* a "nodes" index
* @return the index of the specified "nodes" parent
* @throws IndexOutOfBoundsException
* if {@code index} is less than 1
*/
protected abstract int getParentOf(int index);

/**
* <p>
* This results in the entry at the specified index "bubbling up" to a
* location such that the property of the heap are maintained. This method
* should run in O(log(size)) time.
* </p>
* <p>
* Note: When add is called, an Entry is placed at the end of the internal
* array and then this method is called on that index.
* </p>
*
* @param index
* the index to bubble up
*/
protected abstract void bubbleUp(int index);

/**
* <p>
* This method results in the entry at the specified index "bubbling down"
* to a location such that the property of the heap are maintained. This
* method should run in O(log(size)) time.
* </p>
* <p>
* Note: When remove is called, if there are elements remaining in this
* {@link AbstractArrayHeap} the bottom most element of the heap is placed
* at the 0th index and bubbleDown(0) is called.
* </p>
*
* @param index
*/
protected abstract void bubbleDown(int index);
}

Source code for StudentArrayHeap.Java:

package structures;

import java.util.Comparator;
import java.util.Iterator;

public class StudentArrayHeap<P, V> extends AbstractArrayHeap<P, V> {

   protected StudentArrayHeap(Comparator<P> comparator) {
       super(comparator);
       // TODO Auto-generated constructor stub
   }

   @Override
   protected int getLeftChildOf(int index) {
       // TODO Auto-generated method stub
       if(index < 0) {
           throw new IndexOutOfBoundsException();
       }
       int leftChild = 2*index+1;
       return leftChild;
   }

   @Override
   protected int getRightChildOf(int index) {
       // TODO Auto-generated method stub
       if(index < 0) {
           throw new IndexOutOfBoundsException();
       }
       int rightChild = 2*index+2;
       return rightChild;
   }

   @Override
   protected int getParentOf(int index) {
       // TODO Auto-generated method stub
       if(index < 1) {
           throw new IndexOutOfBoundsException();
       }
       int parent = (index-1)/2;
       return parent;
   }

   @Override
   protected void bubbleUp(int index) {
       // TODO Auto-generated method stub
       int parent = (index-1)/2;
       Entry<P, V> elem = new Entry<P, V>(heap.get(index).getPriority(), heap.get(index).getValue());
      
       while ((index > 0) &&
       this.comparator.compare(heap.get(index).getPriority(), heap.get(parent).getPriority()) > 0 ) {
       swap(index, parent);
           index = parent;
           parent = (parent-1)/2;
       }
       heap.set(index, elem);  
   }

   @Override
   protected void bubbleDown(int index) {
       // TODO Auto-generated method stub
       int largerChild;
       Entry<P, V> elem = new Entry<P, V>(heap.get(index).getPriority(), heap.get(index).getValue());
      
       while (index < size()/2) { // has at least 1 child
           int left = 2*index+1;
           int right = 2*index+2;
           if (right < size() && this.comparator.compare(heap.get(left).getPriority(), heap.get(right).getPriority()) < 0) {
                  largerChild = right;
           }
           else {
           largerChild = left;
           }
           if (this.comparator.compare(heap.get(index).getPriority(), heap.get(largerChild).getPriority()) >= 0) {
               break;
           }
           swap(index, largerChild);
           index = largerChild;
       }
       heap.set(index, elem);
   }
}

Source code for PriorityQueue.Java:

package structures;

import java.util.Comparator;
import java.util.Iterator;

/**
* A {@link PriorityQueue} is a queue data structure that allows elements to be
* enqueued with a priority such that higher priority elements are dequeued
* first.
*
* @param <P>
* the priority type of this {@link PriorityQueue}
* @param <V>
* the value type of this {@link PriorityQueue}
*/
public interface PriorityQueue<P, V> extends Iterable<Entry<P, V>> {

   /**
   * Enqueues the specified {@code value} into this {@link PriorityQueue} with
   * the specified {@code priority}. This runs in O(log(size)) time. For
   * convenience this method returns the modified {@link PriorityQueue}.
   *
   * @param priority
   * the priority of this enqueue
   * @param value
   * the value being enqueued
   * @return the modified {@link PriorityQueue}.
   * @throws NullPointerException
   * if {@code prioirty} is {@code null} or {@code value} is
   * {@code null}.
   */
   public PriorityQueue<P, V> enqueue(P priority, V value);

   /**
   * Removes the value with the highest priority in this {@link PriorityQueue}
   * and then returns it. This runs in O(log(size)) time.
   *
   * @return the value with the highest priority in this {@link PrioirtyQueue}
   * @throws IllegalStateException
   * if this {@link PriorityQueue} is empty.
   */
   public V dequeue();

   /**
   * Returns the value with the highest priority in this {@link PriorityQueue}.
   *
   * @return the value with the highest priority in this {@link PriorityQueue}.
   * @throws IllegalStateException
   * if this {@link PriorityQueue} is empty.
   */
   public V peek();

   /**
   * Returns an {@link Iterator} over all of the entries in this
   * {@link PriorityQueue}. The order of these elements is unspecified and a
   * call to {@link Iterator#remove()} results in an
   * {@link UnsupportedOperationException}.
   *
   * @return an {@link Iterator} over all of the values in this
   * {@link PriorityQueue}.
   */
   public Iterator<Entry<P, V>> iterator();

   /**
   * Returns the {@link Comparator} that is used to determine the ordering of
   * {@link Entry}s in this {@link PriorityQueue}.
   *
   * @return the {@link Comparator} that is used to determine the ordering of
   * {@link Entry}s in this {@link PriorityQueue}.
   */
   public Comparator<P> getComparator();

   /**
   * Returns the total number of elements in this {@link PriorityQueue}
   *
   * @return the total number of elements in this {@link PriorityQueue}
   */
   public int size();

   /**
   * Returns {@code true} if this {@link PrioirtyQueue} has no elements and
   * {@code false} otherwise.
   *
   * @return {@code true} if this {@link PrioirtyQueue} has no elements and
   * {@code false} otherwise.
   */
   public boolean isEmpty();
}

Source code for MinQueue.Java:

package structures;

import comparators.ReverseIntegerComparator;

import java.util.Comparator;
import java.util.Iterator;

public class MinQueue<V> implements PriorityQueue<Integer, V> {

   private StudentArrayHeap<Integer, V> minHeap = new StudentArrayHeap<>(new ReverseIntegerComparator());

   @Override
   public PriorityQueue<Integer, V> enqueue(Integer priority, V value) {
       // TODO Auto-generated method stub
       if(priority == null || value == null) {
           throw new NullPointerException();
       }
       minHeap.add(priority, value);
       return this;
   }

   @Override
   public V dequeue() {
       // TODO Auto-generated method stub
       if(this.isEmpty()) {
           throw new IllegalStateException();
       }
       V val = minHeap.remove();
       return val;
   }

   @Override
   public V peek() {
       // TODO Auto-generated method stub
       return minHeap.peek();
   }

   @Override
   public Iterator<Entry<Integer, V>> iterator() {
       // TODO Auto-generated method stub
       return minHeap.heap.iterator();
   }

   @Override
   public Comparator<Integer> getComparator() {
       // TODO Auto-generated method stub
       return minHeap.getComparator();
   }

   @Override
   public int size() {
       // TODO Auto-generated method stub
       return minHeap.size();
   }

   @Override
   public boolean isEmpty() {
       // TODO Auto-generated method stub
       return minHeap.isEmpty();
   }
}

Source code for MaxQueue.Java:

package structures;

import comparators.IntegerComparator;

import java.util.Comparator;
import java.util.Iterator;

public class MaxQueue<V> implements PriorityQueue<Integer, V> {
  
   private StudentArrayHeap<Integer, V> maxHeap = new StudentArrayHeap<>(new IntegerComparator());

   @Override
   public PriorityQueue<Integer, V> enqueue(Integer priority, V value) {
       // TODO Auto-generated method stub
       if(priority == null || value == null) {
           throw new NullPointerException();
       }
       maxHeap.add(priority, value);
       return this;
   }

   @Override
   public V dequeue() {
       // TODO Auto-generated method stub
       if(this.isEmpty()) {
           throw new IllegalStateException();
       }
       V val = maxHeap.remove();
       return val;
   }

   @Override
   public V peek() {
       // TODO Auto-generated method stub
       return maxHeap.peek();
   }

   @Override
   public Iterator<Entry<Integer, V>> iterator() {
       // TODO Auto-generated method stub
       return maxHeap.heap.iterator();
   }

   @Override
   public Comparator<Integer> getComparator() {
       // TODO Auto-generated method stub
       return maxHeap.getComparator();
   }

   @Override
   public int size() {
       // TODO Auto-generated method stub
       return maxHeap.size();
   }

   @Override
   public boolean isEmpty() {
       // TODO Auto-generated method stub
       return maxHeap.isEmpty();
   }
}

Source code for StringLengthComparator.Java:

package comparators;

import java.util.Comparator;

/**
* A {@link StringLengthComparator} compares strings by their
* length such that shorter string come before longer strings. Strings of the
* same length are sorted lexicographically.
*
*/
public class StringLengthComparator implements Comparator<String> {
   @Override
   public int compare(String arg0, String arg1) {
       if (arg0.length() < arg1.length()) return -1;
       if (arg0.length() > arg1.length()) return 1;
       return arg0.compareTo(arg1);
   }
}

Source code for IntegerComparator.java:

package comparators;

import java.util.Comparator;

/**
* An {@link IntegerComparator} compares integers in the natural way.
*
*/
public class IntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer arg0, Integer arg1) {
// TODO
       if(arg0 > arg1) {
           return 1;
       }
       if(arg0 < arg1) {
           return -1;
       }
       else {
return 0;
       }
}
}

Source code for ReverseIntegerComparator.java:

package comparators;

import java.util.Comparator;

/**
* An {@link ReverseIntegerComparator} compares integers in reverse order,
* e.g., compare(2, 1) returns a negative number.
*
*/
public class ReverseIntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer arg0, Integer arg1) {
// TODO
       if(arg0 > arg1) {
           return -1;
       }
       if(arg0 < arg1) {
           return 1;
       }
       else {
           return 0;
       }
}
}

Source code for Entry.java:

package structures;

/**
* An {@link Entry} describes an element of a {@link PriorityQueue}.
*
* @param <P> the priority type for this {@link Entry}
* @param <V> the value type for this {@link Entry}
*/
public final class Entry<P, V> {
  
   private final P priority;
   private final V value;
  
   /**
   * @param priority
   * @param value
   */
   public Entry(P priority, V value){
if (priority == null || value == null) {
           throw new NullPointerException("The priority and value must be non-null.");
}
       this.priority = priority;
       this.value = value;
   }
  
   /**
   * Returns the priority of this {@link Entry}
   * @return the priority of this {@link Entry}
   */
   public final P getPriority(){
       return priority;
   }
  
   /**
   * Returns the value of this {@link Entry}
   * @return the value of this {@link Entry}
   */
   public final V getValue(){
       return value;
   }
}

Hope it helps, if you like the answer give it a thumbs up. Thank you.