基于最小堆实现优先队列：适配Element类的插入方法修改

Let's work through fixing your insert method to properly handle the Element<T> class and enforce the min-heap property. Here's a breakdown of the issues and step-by-step solutions:

Key Problems in Your Current Code #

• Your heap stores raw T values instead of Element<T> objects (which track both the element and its priority)
• The bubble-up logic is written for a max-heap (you swap when the parent is smaller than the child), but you need a min-heap (swap when the parent has a higher priority than the child)
• Array indexing is inconsistent (you added the first element at index 0, but your heap is designed to start at index 1 for easier parent/child calculations)

Step-by-Step Fixes #

1. Update Heap Storage to Use Element<T> #

First, adjust your class to store Element<T> objects instead of raw T values. This ensures every entry keeps track of both the element and its priority:

package priorityQueue;

import java.util.ArrayList;
import java.util.Comparator;
import priorityQueueInterfaces.PriorityQueue;

public class BinaryHeap<T> implements PriorityQueue<T> {
    private int currentSize = 0;
    private static final int DEFAULT_CAPACITY = 20;
    // Update storage to hold Element<T> instead of raw T
    private ArrayList<Element<T>> array = null;
    private Comparator<? super T> comparator = null;

    // Updated constructor
    public BinaryHeap(Comparator<? super T> comparator) {
        currentSize = 0;
        array = new ArrayList<>(DEFAULT_CAPACITY + 1);
        this.comparator = comparator;
    }

    // Updated constructor for pre-filled heap (now accepts ArrayList<Element<T>>)
    public BinaryHeap(ArrayList<Element<T>> array, Comparator<? super T> comparator) {
        this.currentSize = array.size();
        this.array = new ArrayList<>(array.size() + 1);
        this.comparator = comparator;
        for (int i = 0; i < array.size(); i++) {
            this.array.set(i + 1, array.get(i));
        }
    }

    // Keep your existing swapElements, minHeapify, maxHeapify methods (update them to handle Element<T> if needed)

2. Rewrite the Insert Method #

Modify the insert method to accept Element<T> objects, fix the min-heap bubble-up logic, and correct indexing:

/**
 * Insert an Element (with value and priority) into the min-heap priority queue.
 * Duplicates are allowed.
 * @param element the Element object to insert.
 */
public void insert(Element<T> element) throws PriorityQueueException {
    if (element == null) {
        throw new IllegalArgumentException("Element to be inserted cannot be null!");
    }

    // Extend array if we're running out of space
    if (currentSize + 1 == array.size()) {
        extendArray();
    }

    // Heap starts at index 1, so increment currentSize and use it as the new element's index
    currentSize++;
    int index = currentSize;
    array.set(index, element);

    // Bubble up: swap with parent if parent has higher priority (min-heap rule)
    while (index > 1) {
        int parentIndex = index / 2;
        Element<T> parent = array.get(parentIndex);
        Element<T> current = array.get(index);

        // Compare priorities: swap if parent's priority is greater than current's
        if (comparator.compare(parent.getPriority(), current.getPriority()) > 0) {
            swapElements(index, parentIndex);
            index = parentIndex;
        } else {
            // Heap property is restored, exit loop
            break;
        }
    }
}

// Optional overload: let users insert a value and priority directly (no need to create Element manually)
public void insert(T value, T priority) throws PriorityQueueException {
    insert(new Element<>(value, priority));
}

// Update swapElements to handle Element<T> (your existing logic works, but we'll make it explicit)
private void swapElements(int firstIndex, int secondIndex) throws PriorityQueueException {
    Element<T> temp = array.get(firstIndex);
    array.set(firstIndex, array.get(secondIndex));
    array.set(secondIndex, temp);
}

// Helper method to extend the array when needed
private void extendArray() {
    array.ensureCapacity(array.size() * 2);
}

3. Verify Comparator Behavior #

Make sure your comparator is set up to compare priority values correctly. For example, if your priority is an Integer, use a Comparator<Integer> that sorts in ascending order (this ensures the smallest priority stays at the top of the min-heap).

Why This Works #

• We now store full Element<T> objects, so every entry retains both the element and its priority
• The bubble-up logic correctly enforces the min-heap property: we only swap a child with its parent if the parent has a higher priority (keeping the lowest priority at the root)
• Indexing starts at 1, which simplifies parent/child calculations (parent = index/2, left child = 2*index, right child = 2*index+1)

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