我有一个索引的最低优先级队列实现为堆。删除索引元素时，代码为：
public void delete(int i) {
if (i < 0 || i >= maxN) throw new IllegalArgumentException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, n--);
swim(index); // Why is this needed?
sink(index);
keys[i] = null;
qp[i] = -1;
}
其余代码可在此处找到：https : //algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html
由于pq[N]是中的最后一个元素pq[]，并且与pq[i]（要删除的）处的元素交换，这是否意味着pq[i]交换后的值大于或等于pq[i]交换前的值？问题是，为什么我们必须打电话swim(i)而不是一个sink(i)人打电话呢？swim(i)交换后需要在哪种特定条件下致电？
（有3个阵列，qp[]并keys[]与相应的索引，以及pq[]使得qp[pq[i]]= pq[qp[i]]= i。）
由于pq [N]是pq []中的最后一个元素，并且与pq [i]上的元素交换（将被删除），因此这并不意味着交换后pq [i]上的值交换之前大于或等于pq [i]？
不，那不一定是真的。有效堆的唯一要求是，子级不能大于其父级。虽然这意味着在第一位置的元素是最小的，但它并不意味着在最后位置的元素是最大的。考虑以下堆：
1
10 2
15 18 5 3
16 17 19 20 7 8 6 4
pq[N]是4，但是该堆中有很多元素大于它。假设我们想15通过将其替换为来删除它4。4小于10，因此必须向上移动树（使用swim）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句