从索引优先级队列(java)中删除
从索引优先级队列(java)中删除
提问于 2018-10-15 07:08:06
我有一个作为堆实现的带索引的最低优先级队列。删除索引元素时，代码为：
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。)
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-10-15 12:32:49
由于pqN是pq[]中的最后一个元素，并且它与pqi处的元素交换，这不是意味着交换后pqi处的值大于或等于交换前的pqi吗？
不，这不一定是真的。有效的最小堆的唯一要求是子堆不能小于其父堆。虽然这意味着第一个位置的元素是最小的，但这并不意味着最后一个位置的元素是最大的。考虑以下堆：
1
10 2
15 18 5 3
16 17 19 20 7 8 6 4pq[N]是4，但是堆中有很多比它大的元素。假设我们想通过将15替换为4来删除它。4比10小，因此必须在树中向上移动(使用swim)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52807854
复制相关文章
相似问题