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