代码之家 › 专栏 › 技术社区 › StraightUpBusta

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

indexed priority-queue heap data-structures java

0

StraightUpBusta · 技术社区 · 6 年前

 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] 资格预审 交换大于或等于 资格预审 交换之前?问题是我们为什么要打电话 swim(i) 一点也不只是 sink(i) 游泳(一)

qp[] 和 keys[] 具有相应的索引,以及 pq[] qp[pq[i]] pq[qp[i]] = i

1 回复 | 直到 6 年前

1

2

Misha 6 年前

由于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 小于 10 swim ).