我已经理解了优先队列的概念。但是当涉及到索引优先队列时,我对一些方法的实现有些困惑,比如change(int k, Item item)和delete(int i)。
change(int k, Item item)是将与k相关联的项更改为item
delete(int i)是删除k及其相关联的项
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
我了解下沉和上浮的操作。但是在delete(int i)和changeKey(int i, Key key)方法中,为什么会有
swim(qp[i]/index);
和sink(qp[i]/index);
语句?到底发生了什么?我还想知道优先队列和索引优先队列之间的元素构造方式以及二叉堆中存储了什么?是索引还是元素?