所以我正在学习 Coursera 的算法类(class)(由 Sedgewick 教授,顺便说一句,很棒的类(class)),并且这个“无序数组优先级队列”的某个部分让我感到困惑
public class UnorderedPQ < Item extends Comparable > {
private Comparable[] pq;
private int N;
public UnorderedPQ(int maxN) {
pq = new Comparable[maxN];
}
public boolean isEmpty() {
return N == 0;
}
public void insert(Item x) {
pq[N++] = x;
}
public Item delMax() {
int max = 0;
for (int i = 1; i < N; i++)
if (less(max, i)) max = i;
exch(max, N - 1);
return (Item) pq[--N];
}
}
return (Item) pq[--N];
<---这部分,注释指出“从PQ中删除并返回最大元素”
所以我基本上理解了除了pq[--N]
之外的所有内容,请记住,我基本上也从未做过任何java。
我明白为什么这会返回第 N-1 个数组项......但它到底如何完全删除它。类(class)中说我们这样做是为了“清空条目以防止闲逛”?但我不太确定它是如何工作的?
旁注:知道为什么在 delMax() 的 for 循环中我们从 1 开始吗?我认为这是因为我们要添加到前面,所以我们没有理由检查第一项?
最佳答案
您有两个问题:
1) pq[--N]
如何完全删除该项目?答案是不会。它有效通过递减N
来删除它,因此它不会被视为存在于优先级队列中,但对该Item
的引用是仍然存在于数组pq
中。要完全删除它(并使其符合垃圾回收的条件),数组元素应设置为 null
。我将其归类为内存泄漏。
2) 为什么delMax()
中的循环从1开始?它从1开始的原因是上一行 - int max = 0 ;
— 将元素 0 设置为最大元素。检查元素 0 是否小于其自身是没有意义的。
关于Java返回数组并删除最后一项?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47066359/