Min Heap Priority Queue

Question

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.

• dfhwze: Where does PriorityNode come from?
• Rahul Wadhwani: Apologies! I forgot to add code for PriorityNode. Have added it to the main question

Answer 1

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

• Rahul Wadhwani: 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.
• Peter Taylor: Wouldn't it be less duplicative for add to be if (!offer(item, priority)) throw new IllegalArgumentException();?
• dfhwze: @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/….
• Eric Stein: Java does not have a readonly keyword. Constants are public static final (or whatever the correct access level is).
• Rahul Wadhwani: 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?