问最小堆优先级队列

EN

public class ArrayHeapMinPQ<T> {


   private PriorityNode<T>[] items;
   private int INITIALCAPACITY = 4;
   private int capacity = INITIALCAPACITY;
   private int size = 0;
   private Set<T> itemSet;

   // Declaring a construtor to intialize items as an array of PriorityNodes
   public ArrayHeapMinPQ() {
       itemSet = new HashSet<>();
       items = new PriorityNode[INITIALCAPACITY]; 
       items[0] = new PriorityNode(null, -1);

   }

   /*
    * Adds an item with the given priority value. Throws an
    * IllegalArgumentException if item is already present
    */
   @Override
   public void add(T item, double priority) {
       ensureCapacity();

       // To ensure that duplicate keys are not being used in the queue
       if (itemSet.contains(item)) {
           throw new IllegalArgumentException();
       }

       items[size + 1] = new PriorityNode(item, priority);
       size++;
       itemSet.add(item);
       upwardHeapify(items[size]);
   }

   /*
    * Returns true if the PQ contains the given item
    */
   @Override
   public boolean contains(T item) {
       return itemSet.contains(item); 
   }

   /*
    * Returns the minimum item. Throws NoSuchElementException if the PQ is
    * empty
    */
   @Override
   public T getSmallest() {
       if (this.size == 0) throw new NoSuchElementException();
       return items[1].getItem();
   }

   @Override
   public T removeSmallest() {
       if (this.size == 0) throw new NoSuchElementException();
       T toReturn = items[1].getItem();
       items[1] = items[size];
       items[size] = null;
       size -= 1;
       itemSet.remove(toReturn);
       downwardHeapify();

       ensureCapacity();

       return toReturn;
   }

   // TODO: Implementation of changePriority is pending

    /**
     * Changes the priority of the given item. Throws
     * NoSuchElementException if the element does not exists
     * @param item Item for which the priority would be changed
     * @param priority New priority for the item
     */
   @Override
   public void changePriority(T item, double priority) {
       if (!itemSet.contains(item)) throw new NoSuchElementException();
       for (int i = 1; i <= this.size; i += 1) {
           if (item.equals(items[i].getItem())) {
               PriorityNode currentNode = items[i];
               double oldPriority = currentNode.getPriority();
               currentNode.setPriority(priority);
               if (priority < oldPriority) {
                   upwardHeapify(currentNode);
               }
               else {
                   downwardHeapify();
               }
               break;
           }
       }
   }

   /* Returns the number of items in the PQ */
   @Override
   public int size() {
      return this.size;
   }

    /*
    * Helper function to retrieve left child index of the parent
    */
   private int getLeftChildIndex(int parentIndex) {
       return 2 * parentIndex;    
   }

   /*
    * Helper function to retrieve right child index of the parent
    */
   private int getRightChildIndex(int parentIndex) {
       return 2 * parentIndex + 1;
   }

   /*
    * Helper function retrieve the parent index
    */
   private int getParentIndex(int childIndex) {
       return childIndex / 2;
   }

   /*
    * Helper method to heapify the queue upwards
    */
   private void upwardHeapify(PriorityNode last) {
       PriorityNode smallestNode = items[1];
       // the last node which was inserted in the array
       PriorityNode lastNode = last;
       int latestNodeIndex = size;
       // The max could be that last node will need to switch the smallest node
       while (!lastNode.equals(smallestNode)) {
           // Get the parent node
           int parentNodeIndex = getParentIndex(latestNodeIndex);
           PriorityNode parentNode = items[parentNodeIndex];

           // The function is working because the compareTo method is
           // comparing the priority and not the data in the item
           if (parentNode.compareTo(lastNode) > 0) {
               // Swap the last node with its parent node
               swap(parentNodeIndex, latestNodeIndex);

               // Update the method variables
               latestNodeIndex = parentNodeIndex;
               lastNode = items[latestNodeIndex];
           }
           // The priority of the parent is less than or equal to the parent
           else if (parentNode.compareTo(lastNode) <= 0) {
               break;
           }
       }
   }

   private void downwardHeapify() {
       // assumption is that the top node is the largest node
       int currentIndex = 1;
       while(hasLeftChild(currentIndex)) {
           int leftChildIndex = getLeftChildIndex(currentIndex);
           int smallerChildIndex = leftChildIndex;

           if (hasRightChild(currentIndex)) {
               int rightChildIndex = getRightChildIndex(currentIndex);
               double leftChildPriority = items[leftChildIndex].getPriority();
               double rightChildPriority = items[rightChildIndex].getPriority();

               if (leftChildPriority > rightChildPriority) {
                   smallerChildIndex = rightChildIndex;
               }
           }

           if (items[currentIndex].getPriority() <
                   items[smallerChildIndex].getPriority()) {
               break;
           }
           else {
               swap(currentIndex, smallerChildIndex);
           }
           currentIndex = smallerChildIndex;

       }
   }

   private boolean hasLeftChild(int index) {
       return getLeftChildIndex(index) < this.size + 1;
   }

    private boolean hasRightChild(int index) {
       return getRightChildIndex(index) < this.size + 1;
   }

    /* 
    * Helper function to the class to make sure that there is enough capacity
    * in the array for more elements
    */
   private void ensureCapacity() {
       // there are two conditions to take care of
       // 1. Double the size
       // 2. Make the size half if the array is 3/4 empty
       double currentLoad = (double) this.size / (double) this.capacity;
       int newCapacity = capacity;
       if(this.size > 1 && currentLoad < 0.25) {
           // Array is being downSized
           newCapacity = capacity / 2;
           items = Arrays.copyOf(items, newCapacity);
       }
       else if (currentLoad >= 0.5 ) {
           // Doubling the size of the array
           newCapacity = capacity * 2;
           items = Arrays.copyOf(items, newCapacity);
       }
       capacity = newCapacity;
   }

   /*
    * Helper method to swap two nodes
    */
   private void swap(int parentNodeIndex, int latestNodeIndex) {
       PriorityNode temp = items[parentNodeIndex];
       items[parentNodeIndex] = items[latestNodeIndex]; 
       items[latestNodeIndex] = temp;
   }

   public Integer[] toArray() {
       Integer[] toReturn = new Integer[items.length];
       for (int i = 1; i < items.length - 1; i++) {
           toReturn[i] = ((Double) items[i].getPriority()).intValue();
       }
       return toReturn;
   }

}

public class PriorityNode<T> implements Comparable<PriorityNode> {

    private T item;
    private double priority;

    PriorityNode(T item, double priority) {
        this.item = item;
        this.priority = priority;
    }

    protected T getItem() {
        return this.item;
    }

    protected double getPriority() {
        return this.priority;
    }

    protected void setPriority(double priority) {
        this.priority = priority;
    }

    @Override
    public int compareTo(PriorityNode other) {
        if (other == null) {
            return -1;
        }
        return Double.compare(this.getPriority(), other.getPriority());
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object o) {
        if (o == null || o.getClass() != this.getClass()) {
            return false;
        }
        else {
            return ((PriorityNode) o).getItem().equals(this.getItem());
        }
    }

    @Override
    public int hashCode() {
        return item.hashCode();
    }
}