从索引优先级队列中删除 (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]？不，这不一定是真的。有效堆的唯一要求是子级不能大于其父级。虽然这意味着在第一位置的元素是最小的，但它并不意味着在最后位置的元素是最大的。考虑以下堆：&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; 10&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;2&nbsp;&nbsp;&nbsp; 15&nbsp; &nbsp; &nbsp; &nbsp;18&nbsp; &nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; &nbsp; 316&nbsp; 17&nbsp; &nbsp;19&nbsp; 20&nbsp; &nbsp; 7&nbsp; &nbsp;8&nbsp; &nbsp; 6&nbsp; &nbsp;4pq[N]是4，但该堆中有很多元素比它大。假设我们想15通过将其替换为 来删除4。 4小于10，因此必须向上移动树（使用swim）。