gpt4 book ai didi

java - 索引优先队列的困惑

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:31:59 25 4
gpt4 key购买 nike

优先级队列的概念我已经有了。但是说到索引优先级队列的时候,对于change(int k, Item item)delete(int i)

change(int k, Item item) is to change the item associated with k to item

delete(int i) is to remove k and its associated item

public void changeKey(int i, Key key) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}

public void delete(int i) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, n--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}

private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}


private int maxN; // maximum number of elements on PQ
private int n; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; // keys[i] = priority of i

我理解sinkswim的操作,但是为什么在方法delete(int i)changeKey(int i,Key key) 有语句 swim(qp[i]/index);sink(qp[i]/index);到底是什么发生了什么?

而且我还想知道优先级队列和索引优先级队列的元素构造方式以及索引优先级队列的二叉堆中存储的是什么?索引还是元素?

最佳答案

这些是在您更改 key 时需要执行的二进制堆上的操作。优先级队列中的每个“节点”都保存在二进制堆中。当您添加一个项目时,该项目需要放置在正确的位置,因此不会违反“二叉堆规则”。

更改 key 时也会发生同样的情况,您需要更改项目在优先级堆中的位置,这样规则就不会被破坏(该项目的子项不大于它,并且该项目的父项不小于它)。

这个优先级队列是用二叉堆实现的,也就是说它是基于二叉树的,这就是为什么你可以在那些方法中看到被2除的原因,因为它需要逐级向上/向下取项,这是实现的通过该除法(第一级有一个节点,第二级有两个节点,第三级有四个节点等,节点数每级乘以2)。

这篇文章只是对一个庞大而广泛的主题的介绍,我建议阅读更多相关内容(尤其是“heapify”部分):check this out.

一般来说,重点是您只有一种更改 key 的方法,它会调用 swimsink,因为前一个 key 可能更高或更低。它通常使用 2 个方法完成:decreaseKeyincreaseKey,每个方法只调用一个 - sinkswim >,因此。您的代码将这 2 个方法合并为 1 个,这就是它同时调用 sinkswim 的原因。当新 key 高于旧 key 时,意味着它需要在堆中上升(swim),当新 key 低于旧 key 时,它需要下降(下沉).

顺便说一句,我的整篇文章都假设我们正在使用最大堆 - 这意味着根节点具有最大值而他的子节点具有较小的值等。还有一个完全相反的最小堆。

关于java - 索引优先队列的困惑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39572388/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com