从索引优先级队列 (java) 中删除

Question

我有一个索引最低优先级队列作为堆实现。删除索引元素时，代码为：

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。

Answer 1

由于 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(。