Java泛型列表实现二叉堆：1-based与0-based索引的挑战与解决方案

public class Lecture17<T> {
    private Comparator<T> cc;
    private List<T> myQueue; // 0-based list

    public Lecture17(Comparator<T> cc) {
        this.cc = cc;
        this.myQueue = new ArrayList<>();
        this.myQueue.add(0, null); // 占位符，使实际元素从索引1开始
    }

    // ... 其他辅助方法如 Smallerthan, swap, sink ...

    public T deleteMax() { // 移除优先级最高的元素
        // 假设 myQueue 实际存储的元素从索引1开始
        T highestPriorityItem = this.myQueue.get(1); // 获取堆顶元素

        // 将最后一个元素移动到堆顶
        // 错误：this.myQueue.size() 返回的是列表的长度，而不是最后一个元素的索引
        this.myQueue.set(1, this.myQueue.get(this.myQueue.size())); 

        // 错误：试图将 myQueue.size() 处的元素设为 null，但该索引可能越界
        this.myQueue.set(this.myQueue.size(), null); // 防止对象游离 (loitering)

        // size()--; // 假设有一个 size 实例变量来跟踪实际元素数量
        sink(1); // 恢复堆序

        return highestPriorityItem;
    }
}

public class Lecture17<T> {
    private Comparator<T> cc;
    private List<T> myQueue; // 0-based list
    private int N; // 维护堆中实际元素的数量，不包括索引0的null

    public Lecture17(Comparator<T> cc) {
        this.cc = cc;
        this.myQueue = new ArrayList<>();
        this.myQueue.add(null); // 索引0处占位符
        this.N = 0; // 初始时堆为空
    }

    // 辅助方法，用于比较元素大小
    private boolean Smallerthan(int v, int w) {
        return (cc.compare(this.myQueue.get(v), this.myQueue.get(w)) < 0);
    }

    // 交换两个位置的元素
    private void swap(int i, int j) {
        T temp = this.myQueue.get(i);
        this.myQueue.set(i, this.myQueue.get(j));
        this.myQueue.set(j, temp);
    }

    // 下沉操作，恢复堆序
    private void sink(int z) {
        // 循环条件应基于 N (实际元素数量)，而不是 myQueue.size()
        while (2 * z <= N) { 
            int j = 2 * z;
            // 确保 j+1 不越界，且比较的是实际元素
            if ((j < N) && Smallerthan(j, j + 1)) 
                j++;
            if (!Smallerthan(z, j)) // 如果父节点不小于子节点，则停止下沉
                break;
            swap(z, j);
            z = j; // 更新当前节点位置
        }
    }

    // 获取堆中元素数量
    public int size() {
        return N;
    }

    // 移除优先级最高的元素
    public T deleteMax() {
        if (N == 0) {
            return null; // 堆为空
        }
        T highestPriorityItem = this.myQueue.get(1); // 获取堆顶元素

        // 将最后一个元素移动到堆顶
        // 正确：使用 N 获取最后一个元素的索引
        swap(1, N); 

        this.myQueue.set(N, null); // 防止对象游离，并将 N 处的元素设为 null
        N--; // 更新堆的逻辑大小

        // 由于 ArrayList 动态调整大小，这里直接移除最后一个元素更干净
        // this.myQueue.remove(this.myQueue.size() - 1); // 如果不需要保留null占位，可以直接移除

        sink(1); // 恢复堆序

        return highestPriorityItem;
    }

    // 插入元素 (为完整性补充)
    public void insert(T item) {
        if (myQueue.size() == N + 1) { // 检查是否需要扩容
            myQueue.add(null); // 简单扩容
        }
        N++;
        myQueue.set(N, item);
        swim(N); // 上浮操作
    }

    // 上浮操作 (为完整性补充)
    private void swim(int k) {
        while (k > 1 && Smallerthan(k/2, k)) {
            swap(k/2, k);
            k = k/2;
        }
    }
}

public class Lecture17_0Based<T> {
    private Comparator<T> cc;
    private List<T> myQueue; // 0-based list

    public Lecture17_0Based(Comparator<T> cc) {
        this.cc = cc;
        this.myQueue = new ArrayList<>(); // 索引0将存放根节点
    }

    // 辅助方法，用于比较元素大小
    private boolean Smallerthan(int v, int w) {
        return (cc.compare(this.myQueue.get(v), this.myQueue.get(w)) < 0);
    }

    // 交换两个位置的元素
    private void swap(int i, int j) {
        T temp = this.myQueue.get(i);
        this.myQueue.set(i, this.myQueue.get(j));
        this.myQueue.set(j, temp);
    }

    // 获取堆中元素数量
    public int size() {
        return myQueue.size();
    }

    // 下沉操作，恢复堆序 (0-based)
    private void sink(int z) {
        int N = myQueue.size();
        while ((2 * z) + 1 < N) { // 左子节点必须在范围内
            int j = (2 * z) + 1; // 默认左子节点
            if ((j + 1 < N) && Smallerthan(j, j + 1)) // 如果右子节点存在且更大
                j++;
            if (!Smallerthan(z, j)) // 如果父节点不小于子节点，则停止下沉
                break;
            swap(z, j);
            z = j; // 更新当前节点位置
        }
    }

    // 上浮操作 (0-based)
    private void swim(int k) {
        while (k > 0 && Smallerthan((k - 1) / 2, k)) {
            swap((k - 1) / 2, k);
            k = (k - 1) / 2;
        }
    }

    // 插入元素 (0-based)
    public void insert(T item) {
        myQueue.add(item); // 直接添加到列表末尾
        swim(myQueue.size() - 1); // 对新插入的元素执行上浮操作
    }

    // 移除优先级最高的元素 (0-based)
    public T deleteMax() {
        if (myQueue.isEmpty()) {
            return null;
        }
        T highestPriorityItem = myQueue.get(0); // 获取堆顶元素 (索引0)
        int lastIndex = myQueue.size() - 1;

        swap(0, lastIndex); // 将最后一个元素与堆顶元素交换
        myQueue.remove(lastIndex); // 移除最后一个元素 (原堆顶元素)

        if (!myQueue.isEmpty()) { // 如果堆不为空，则对新的堆顶元素执行下沉操作
            sink(0);
        }
        return highestPriorityItem;
    }
}