基于ArrayList实现优先队列插入方法出现重复插入问题求助

Let's break down why you're seeing duplicate elements and fix the code step by step.

The Root Cause: Using ArrayList.add() Instead of ArrayList.set() #

Your code relies on queue.add() in both insert() and siftUp(), but add() inserts a new element at the specified index—it doesn't replace existing elements. This means every call to add() increases the ArrayList's size and adds duplicate copies of elements, instead of moving elements to maintain the heap structure.

Let's walk through your single-element test case to see the duplication happen:

1. When you first call insert(element), queue.size() is 0. queue.add(0, element) inserts the element at index 0, so the queue now has 1 element.
2. You then call siftUp(0) (since size()-1 equals 0). The loop doesn't run because size > 0 is false.
3. Finally, you run queue.add(size, elem)—which adds the same element again at index 0. Now the queue has 2 identical elements, hence the duplication.

Fixed Code for Priority Queue Insert & SiftUp #

Here's the corrected version of your methods, using set() to replace elements instead of inserting duplicates:

// Corrected insert method
public void insert(E element) {
    // Add the new element to the END of the ArrayList first
    queue.add(element);
    // Sift it up to its correct position in the heap
    siftUp(queue.size() - 1);
}

// Corrected siftUp method
public void siftUp(int index) {
    E elem = queue.get(index);
    int parentIndex;
    
    // Keep moving up while the current element is larger than its parent (for max-heap)
    while (index > 0) {
        parentIndex = index / 2;
        E parentElem = queue.get(parentIndex);
        
        // Stop if current element is not larger than parent (adjust comparison for min-heap if needed)
        if (elem.compareTo(parentElem) <= 0) {
            break;
        }
        
        // Move parent element down to current index (replace, don't insert)
        queue.set(index, parentElem);
        index = parentIndex;
    }
    
    // Place the current element in its correct position
    queue.set(index, elem);
}

Key Changes Explained #

1. Insert Method: We add the new element directly to the end of the ArrayList with queue.add(element)—this is the standard starting point for heap insertion. Then we sift it up to maintain heap order.
2. SiftUp Method:
   • Use queue.set(index, parentElem) to move the parent element down to the current index—this replaces the existing element instead of adding a new one.
   • After finding the correct position for the inserted element, we use queue.set(index, elem) to place it there, ensuring no duplicates are added.
   • Adjusted the loop logic for clarity, but the core heap logic (comparing to parent) remains the same for a max-heap. If you need a min-heap, just reverse the comparison (elem.compareTo(parentElem) >= 0).

Additional Notes #

• Make sure your queue is initialized as an empty ArrayList<E> before any inserts.
• Double-check the comparison logic in siftUp to match your priority queue type (max-heap vs min-heap).

内容的提问来源于stack exchange，提问作者JimBelushi2