4
\$\begingroup\$

This was a part of one an assignment I found online and tried to solve it myself.

The objective was to implement a Priority Queue using Min Heap and use Array as the underlying data structure to store the data.

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;
   }

}

PriorityNode

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();
    }
}

I had to implement an interface and I have omitted that part in the code. In my opinion, the change priority function is running at \$O(n)\$ and I am not sure how can I improve the performance of it.

I am looking for a discussion on the code in general and the performance of changePriority function.

\$\endgroup\$
  • \$\begingroup\$ Where does PriorityNode come from? \$\endgroup\$ – dfhwze Aug 18 at 18:57
  • \$\begingroup\$ Apologies! I forgot to add code for PriorityNode. Have added it to the main question \$\endgroup\$ – Rahul Wadhwani Aug 18 at 19:01
3
\$\begingroup\$

General Review

Make all instance fields that are never reassigned final. From the comments you suggest some of these fields get reassigned later in the code. In this case, those fields should not be declared final.

 private final PriorityNode<T>[] items;
 private final Set<T> itemSet;

Make constants static and readonly, and use underscores for readability.

 private static final int INITIAL_CAPACITY = 4;
 private int capacity = INITIAL_CAPACITY;

Don't introduce unnecessary new lines. For instance, between class definition and instance variables. Zero or one new line would suffice.

public class ArrayHeapMinPQ<T> {


   private PriorityNode<T>[] items;
public class ArrayHeapMinPQ<T> {
   private PriorityNode<T>[] items;

Don't write comments that state the obvious. It's polluting the source code. Write comments for when they would really make sense.

   // Declaring a construtor to intialize items as an array of PriorityNodes
   public ArrayHeapMinPQ() {

Like public API comments (this is a good thing):

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

Perform argument checks before changing the state of the instance. (And remove these comments that have zero added value)

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();
       }
public void add(T item, double priority) {
       if (itemSet.contains(item)) {
           throw new IllegalArgumentException();
       }
       ensureCapacity();

It is custom in Java to provide not just add, but also offer methods. add throws an exception, while offer returns a boolean. To accomodate multiple entrypoints, you should put the actual insertion of data in a private method.

private void insert(T item, double priority) {
    ensureCapacity();
    items[size + 1] = new PriorityNode(item, priority);
    size++;
    itemSet.add(item);
    upwardHeapify(items[size]);
}

And then refactor add:

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

And introduce offer:

   /*
    * Adds an item with the given priority value. Returns
    * False if item is already present
    */
   public boolean offer(T item, double priority) {
       if (itemSet.contains(item)) {
           return false;
       }
       insert(item, priority);
       return true;
   }
\$\endgroup\$
  • 2
    \$\begingroup\$ Thank you so much for the great feedback and for helping me improve. The offer methods bit was completely new to me. I will certainly follow this advice in all my code hereupon. Highly appreciate you spending time in reading my code and giving me feedback. \$\endgroup\$ – Rahul Wadhwani Aug 18 at 19:21
  • \$\begingroup\$ Wouldn't it be less duplicative for add to be if (!offer(item, priority)) throw new IllegalArgumentException();? \$\endgroup\$ – Peter Taylor Aug 19 at 8:58
  • \$\begingroup\$ @PeterTaylor Well, that's an option, but the way the Java classes internally work, is that the public methods call the private one: fuseyism.com/classpath/doc/java/util/concurrent/…. \$\endgroup\$ – dfhwze Aug 19 at 10:00
  • 1
    \$\begingroup\$ Java does not have a readonly keyword. Constants are public static final (or whatever the correct access level is). \$\endgroup\$ – Eric Stein Aug 19 at 19:10
  • \$\begingroup\$ If I am declaring items to be final my code stops working. The variable items gets updated in the code later. Should I still try to work around to make it final? \$\endgroup\$ – Rahul Wadhwani Aug 21 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.