Handling Duplicate Values in a Custom Priority Queue Implementation in Java
I'm converting an old project and I've been banging my head against this for hours. I'm currently working on a project where I need to implement a custom priority queue in Java, specifically using a min-heap structure. My implementation works well for the most part, but I'm running into issues when it comes to handling duplicate values. For instance, when I insert multiple elements with the same priority, I want to ensure that they are processed in the order they were added. However, my current implementation doesn't seem to maintain the insertion order when two elements have the same priority. Here's a snippet of the current code for my priority queue: ```java import java.util.ArrayList; import java.util.Comparator; public class CustomPriorityQueue<T> { private ArrayList<T> heap; private Comparator<T> comparator; public CustomPriorityQueue(Comparator<T> comparator) { this.heap = new ArrayList<>(); this.comparator = comparator; } public void insert(T element) { heap.add(element); bubbleUp(heap.size() - 1); } private void bubbleUp(int index) { while (index > 0) { int parentIndex = (index - 1) / 2; if (comparator.compare(heap.get(index), heap.get(parentIndex)) >= 0) { break; } swap(index, parentIndex); index = parentIndex; } } private void swap(int i, int j) { T temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); } public T remove() { if (heap.isEmpty()) return null; T removed = heap.get(0); heap.set(0, heap.remove(heap.size() - 1)); bubbleDown(0); return removed; } private void bubbleDown(int index) { while (index < heap.size()) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int smallest = index; if (leftChild < heap.size() && comparator.compare(heap.get(leftChild), heap.get(smallest)) < 0) { smallest = leftChild; } if (rightChild < heap.size() && comparator.compare(heap.get(rightChild), heap.get(smallest)) < 0) { smallest = rightChild; } if (smallest == index) break; swap(index, smallest); index = smallest; } } } ``` I've tried modifying the comparator to account for insertion order by including a timestamp as a secondary comparison criterion, but it hasn't resolved the issue effectively. Specifically, I'm using this comparator: ```java Comparator<MyElement> myComparator = (e1, e2) -> { if (e1.getPriority() == e2.getPriority()) { return Long.compare(e1.getTimestamp(), e2.getTimestamp()); // Assuming `getTimestamp()` returns the insertion time } return Integer.compare(e1.getPriority(), e2.getPriority()); }; ``` Even with this approach, I still observe unexpected behavior where elements with the same priority are not processed in the expected order. I'm getting inconsistent results and would appreciate any insights on how to ensure that the insertion order is maintained for duplicates. Has anyone faced this issue before, or can you suggest a better approach to handle duplicates in a priority queue implementation? This is part of a larger service I'm building. I'm working on a CLI tool that needs to handle this. Any help would be greatly appreciated! Any advice would be much appreciated.