Modify the implementation of the MinHeap class so that the 0 element of the array is not wasted.

Complete the following file:

MinHeap.java

// TODO: Reorganize the code so that the 0 entry of the array is not wasted. import java.util.*; /** This class implements a heap. */ public class MinHeap { private ArrayList<Comparable> elements; /** Constructs an empty heap. */ public MinHeap() { elements = new ArrayList<Comparable>(); elements.add(null); } /** Adds a new element to this heap. @param newElement the element to add */ public void add(Comparable newElement) { // Add a new leaf elements.add(null); int index = elements.size() - 1; // Demote parents that are larger than the new element while (index > 1 && getParent(index).compareTo(newElement) > 0) { elements.set(index, getParent(index)); index = getParentIndex(index); } // Store the new element into the vacant slot elements.set(index, newElement); } /** Gets the minimum element stored in this heap. @return the minimum element */ public Comparable peek() { return elements.get(1); } /** Removes the minimum element from this heap. @return the minimum element */ public Comparable remove() { Comparable minimum = elements.get(1); // Remove last element int lastIndex = elements.size() - 1; Comparable last = elements.remove(lastIndex); if (lastIndex > 1) { elements.set(1, last); fixHeap(); } return minimum; } /** Turns the tree back into a heap, provided only the root node violates the heap condition. */ private void fixHeap() { Comparable root = elements.get(1); int lastIndex = elements.size() - 1; // Promote children of removed root while they are larger than last int index = 1; boolean more = true; while (more) { int childIndex = getLeftChildIndex(index); if (childIndex <= lastIndex) { // Get smaller child // Get left child first Comparable child = getLeftChild(index); // Use right child instead if it is smaller if (getRightChildIndex(index) <= lastIndex && getRightChild(index).compareTo(child) < 0) { childIndex = getRightChildIndex(index); child = getRightChild(index); } // Check if larger child is smaller than root if (child.compareTo(root) < 0) { // Promote child elements.set(index, child); index = childIndex; } else { // Root is smaller than both children more = false; } } else { // No children more = false; } } // Store root element in vacant slot elements.set(index, root); } /** Returns the number of elements in this heap. */ public int size() { return elements.size() - 1; } /** Returns the index of the left child. @param index the index of a node in this heap @return the index of the left child of the given node */ private static int getLeftChildIndex(int index) { return 2 * index; } /** Returns the index of the right child. @param index the index of a node in this heap @return the index of the right child of the given node */ private static int getRightChildIndex(int index) { return 2 * index + 1; } /** Returns the index of the parent. @param index the index of a node in this heap @return the index of the parent of the given node */ private static int getParentIndex(int index) { return index / 2; } /** Returns the value of the left child. @param index the index of a node in this heap @return the value of the left child of the given node */ private Comparable getLeftChild(int index) { return elements.get(2 * index); } /** Returns the value of the right child. @param index the index of a node in this heap @return the value of the right child of the given node */ private Comparable getRightChild(int index) { return elements.get(2 * index + 1); } /** Returns the value of the parent. @param index the index of a node in this heap @return the value of the parent of the given node */ private Comparable getParent(int index) { return elements.get(index / 2); } }

Use the following files:

HeapDemo.java

/**
   This program demonstrates the use of a heap as a priority queue.
*/
public class HeapDemo
{
   public static void main(String[] args)
   {
      MinHeap q = new MinHeap();
      q.add(new WorkOrder(3, "Shampoo carpets"));
      q.add(new WorkOrder(7, "Empty trash"));
      q.add(new WorkOrder(8, "Water plants"));
      q.add(new WorkOrder(10, "Remove pencil sharpener shavings"));
      q.add(new WorkOrder(6, "Replace light bulb"));
      q.add(new WorkOrder(1, "Fix broken sink"));
      q.add(new WorkOrder(9, "Clean coffee maker"));
      q.add(new WorkOrder(2, "Order cleaning supplies"));

      while (q.size() > 0)
         System.out.println(q.remove());      
   }
}

WorkOrder.java

/**
   This class encapsulates a work order with a priority.
*/
public class WorkOrder implements Comparable
{
   private int priority;
   private String description;

   /**
      Constructs a work order with a given priority and description.
      @param aPriority the priority of this work order
      @param aDescription the description of this work order
   */
   public WorkOrder(int aPriority, String aDescription)
   {
      priority = aPriority;
      description = aDescription;
   }

   public String toString()
   {
      return "priority=" + priority + ", description=" + description;
   }

   public int compareTo(Object otherObject)
   {
      WorkOrder other = (WorkOrder) otherObject;
      if (priority < other.priority) return -1;
      if (priority > other.priority) return 1;
      return 0;
   }
}