Question

Write a method called removeDuplicates that accepts a PriorityQueue of integers as a parameter and modifies the queue’s 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;
}

}

Answer 1

import java.util.stream.Collectors;

public class TestMain {

// method to remove Duplicates from priority queue

public static HeapIntPriorityQueue removeDuplicates(HeapIntPriorityQueue queue) {

Stack<Integer> auxiliary = new Stack<Integer>();

while (!queue.isEmpty()) {

int n = queue.remove();

auxiliary.push(n);

}

for(Integer no: auxiliary.stream().collect(Collectors.toSet())) {

queue.add(no);

}

return queue;

}

// main method to test data

public static void main(String[] args) {

HeapIntPriorityQueue obj = new HeapIntPriorityQueue();

obj.add(7);

obj.add(7);

obj.add(8);

obj.add(8);

obj.add(8);

obj.add(10);

obj.add(45);

obj.add(45);

obj = removeDuplicates(obj);

System.out.println(obj);

}

}

Please find formatted code and output in screenshot