索引优先级队列的混乱

Question

我已经有了优先级队列的概念，但是当涉及到索引优先级队列时，我对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

Answer 1

这些是在更改键时需要在二进制堆上执行的操作。优先级队列中的每个“节点”都保留在二进制堆中。当你添加一个项目时，该项目需要被定位在正确的位置，这样‘二进制堆的规则’就不会被打破。

更改键也会发生同样的情况，您需要更改项在优先级堆中的位置，这样规则就不会被破坏（项的子项不会比它大，项的父项不会比它小）。

这个优先级队列是用一个二进制堆实现的，这意味着它是基于二叉树的，这就是为什么你可以在那些方法中看到除以2，因为它需要逐级向上/向下取项目，这是通过除以实现的（第一级有一个节点，第二级有两个节点，第三级有四个节点等，每个级别的节点数乘以2）。

这篇文章只是对一个巨大而广泛的主题的介绍，我建议阅读更多关于它的内容（特别是“heapify”部分）：看看这个。

通常情况下，关键是您只有一个更改键的方法，并且它同时调用swim和sink，因为前面的键可能更高或更低。通常通过两个方法来完成:dreduceKey和increaseKey，相应地，每一个方法只调用一个-sink或swim。您的代码将这2个方法合并为1个方法，这就是它同时调用sink和swim的原因。当新键高于旧键时，这意味着它需要在堆中上升(swim)；当新键低于旧键时，它需要下降(sink)。

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