Write a method called kthSmallest that accepts a PriorityQueue of integers and an integer k as parameters and returns the k th-smallest integer from the priority queue. For example, if the queue passed stores the integers [42, 50, 45, 78, 61] and k is 4, return the fourth-smallest integer, which is 61. If k is 0 or negative or greater than the size of the queue, throw an IllegalArgumentException. If your method modifies the state of the queue during its computation, it should restore the queue before it returns. You may use one stack or queue as auxiliary storage.

Please also create a Main Program to test the code.

Provided File

******************************

HeapIntPriorityQueue.java

******************************

import java.util.Arrays; import java.util.NoSuchElementException;

// Implements a priority queue of integers using a // min-heap represented as an array. public class HeapIntPriorityQueue { private int[] elementData; private int size; // Constructs an empty queue. public HeapIntPriorityQueue() { elementData = new int[10]; size = 0; } // Adds the given element to this queue. public void add(int value) { // resize if necessary if (size + 1 >= elementData.length) { elementData = Arrays.copyOf(elementData, elementData.length * 2); } // insert as new rightmost leaf elementData[size + 1] = value; // "bubble up" toward root as necessary to fix ordering int index = size + 1; boolean found = false; // have we found the proper place yet? while (!found && hasParent(index)) { int parent = parent(index); if (elementData[index] < elementData[parent]) { swap(elementData, index, parent(index)); index = parent(index); } else { found = true; // found proper location; stop the loop } } size++; } // Returns true if there are no elements in this queue. public boolean isEmpty() { return size == 0; } // Returns the minimum value in the queue without modifying the queue. // If the queue is empty, throws a NoSuchElementException. public int peek() { if (isEmpty()) { throw new NoSuchElementException(); } return elementData[1]; } // Removes and returns the minimum value in the queue. // If the queue is empty, throws a NoSuchElementException. public int remove() { int result = peek();

// move rightmost leaf to become new root elementData[1] = elementData[size]; size--; // "bubble down" root as necessary to fix ordering int index = 1; boolean found = false; // have we found the proper place yet? while (!found && hasLeftChild(index)) { int left = leftChild(index); int right = rightChild(index); int child = left; if (hasRightChild(index) && elementData[right] < elementData[left]) { child = right; } if (elementData[index] > elementData[child]) { swap(elementData, index, child); index = child; } else { found = true; // found proper location; stop the loop } } return result; } // Returns the number of elements in the queue. public int size() { return size; } // Returns a string representation of this queue, such as "[10, 20, 30]"; // The elements are not guaranteed to be listed in sorted order. public String toString() { String result = "["; if (!isEmpty()) { result += elementData[1]; for (int i = 2; i <= size; i++) { result += ", " + elementData[i]; } } return result + "]"; } // helpers for navigating indexes up/down the tree private int parent(int index) { return index / 2; } // returns index of left child of given index private int leftChild(int index) { return index * 2; } // returns index of right child of given index private int rightChild(int index) { return index * 2 + 1; } // returns true if the node at the given index has a parent (is not the root) private boolean hasParent(int index) { return index > 1; } // returns true if the node at the given index has a non-empty left child private boolean hasLeftChild(int index) { return leftChild(index) <= size; } // returns true if the node at the given index has a non-empty right child private boolean hasRightChild(int index) { return rightChild(index) <= size; } // switches the values at the two given indexes of the given array private void swap(int[] a, int index1, int index2) { int temp = a[index1]; a[index1] = a[index2]; a[index2] = temp; } }