Question
Write a method called removeDuplicates that accepts a PriorityQueue of integers as a parameter and modifies the queues state so that any element that is
Write a method called removeDuplicates that accepts a PriorityQueue of integers as a parameter and modifies the queues state so that any element that is equal to another element in the queue is removed. For example, if the queue stores [7, 7, 8, 8, 8, 10, 45, 45], your method should modify the queue to store [7, 8, 10, 45]. 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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started