从索引优先级队列中删除 (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)？ swap后在什么特定情况下需要调用swim(i)？

(有3个数组，qp[]和keys[]有相应的索引，pq[]使得qp[pq[i]] = pq[qp[i]] = i.)

Answer 1

Since pq[N] is the last element in pq[], and this is swapped with the element at pq[i] (which is to be deleted), wouldn't this mean that the value at pq[i] after the swap is larger or equal to pq[i] before the swap?

不，那不一定是真的。有效最小堆的唯一要求是子堆不能小于其父堆。虽然这意味着第一个位置的元素是最小的，但 而不是 意味着最后一个位置的元素是最大的。考虑以下堆：

                1
      10                 2  
  15       18        5        3
16  17   19  20    7   8    6   4

pq[N] 是 4，但该堆中有很多元素比它大。假设我们想通过用 4 替换它来删除 15。 4 小于 10，因此必须向上移动树（使用 swim）。

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

Deleting from Indexed Priority Queue (java)

java

heap

indexed

priority-queue

data-structures