如何反向遍历泛型List<T>？优先队列deleteMax及找最小元素问题

下面是几种实用的反向遍历方案：

• 方法1：普通for循环逆序遍历
  直接从列表最后一个元素的索引（list.size() - 1）开始，遍历到索引0，按需执行操作：

List<T> list = ...; // 你的泛型列表
for (int i = list.size() - 1; i >= 0; i--) {
    T element = list.get(i);
    // 执行自定义操作，比如打印、元素转换等
    System.out.println(element);
}

• 方法2：使用ListIterator逆序遍历
  利用ListIterator的双向遍历能力，从列表末尾开始反向遍历：

List<T> list = ...;
ListIterator<T> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
    T element = iterator.previous();
    // 执行自定义操作
}

• 方法3：Java 8+ 流式API（不修改原列表）
  通过复制列表并反转的方式，在不改变原列表顺序的前提下逆序处理元素：

List<T> list = ...;
new ArrayList<>(list).reverse().forEach(element -> {
    // 执行自定义操作
});

先修复deleteMax()方法的问题 #

你的代码存在几处逻辑和实现漏洞，以下是修正后的完整方案：

1. 补充缺失的swap方法
   sink()方法依赖的交换逻辑未实现，需要添加：

private void swap(int i, int j) {
    T temp = myQueue.get(i);
    myQueue.set(i, myQueue.get(j));
    myQueue.set(j, temp);
}

2. 修正size变量维护
   原代码用索引0存null，实际元素从索引1开始，建议单独维护size变量避免混淆：

// 新增实例变量
private int size;

// 修改构造函数
public Lecture17(Comparator<T> cc) {
    this.cc = cc;
    this.myQueue = new ArrayList<>();
    this.myQueue.add(null); // 索引0占位
    this.size = 0; // 初始元素数量为0
}

3. 修正deleteMax()核心逻辑

public T deleteMax() {
    if (size == 0) throw new NoSuchElementException("Queue is empty");
    
    T highestPriorityItem = myQueue.get(1);
    // 将最后一个元素移到堆顶
    myQueue.set(1, myQueue.get(1 + size));
    // 移除最后一个元素并更新size
    myQueue.remove(1 + size);
    size--;
    // 下沉堆顶元素修复堆结构
    sink(1);
    
    return highestPriorityItem;
}

4. 修正sink()方法的循环条件
   基于维护的size变量判断，避免受索引0的干扰：

private void sink(int z) {
    while (2 * z <= size) {
        int j = 2 * z;
        // 选择左右子节点中较大的那个
        if (j < size && Smallerthan(j, j+1)) {
            j++;
        }
        // 当前节点大于等于子节点，无需继续下沉
        if (!Smallerthan(z, j)) {
            break;
        }
        swap(z, j);
        z = j;
    }
}

查找优先队列中的最小元素 #

你的实现是最大堆，最小元素必然在叶子节点中（堆的性质：父节点优先级高于子节点，叶子节点无后续子节点，是最小候选）。叶子节点的起始索引为size/2 + 1，遍历所有叶子节点即可找到最小元素：

public T findMin() {
    if (size == 0) throw new NoSuchElementException("Queue is empty");
    
    int minIndex = size; // 从最后一个叶子节点开始对比
    for (int i = size/2 + 1; i <= size; i++) {
        if (cc.compare(myQueue.get(i), myQueue.get(minIndex)) < 0) {
            minIndex = i;
        }
    }
    return myQueue.get(minIndex);
}

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