从索引优先级队列中删除 (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[]，并且它与元素 at 交换pq[i]（将被删除），这是否意味着pq[i]交换后的值大于或等于pq[i]交换前的值？问题是为什么我们必须打电话swim(i)而不是sink(i)单独打电话？什么情况下需要swim(i)在swap后调用？（有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）。