索引优先队列的困惑

Question

关于索引优先级队列，我已经有了优先级的想法queue.But，我对一些方法的实现有点困惑，比如change(int k , Item item) and 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

我理解sink和swim的操作。但是为什么在方法delete(int i) 和 changeKey(int i,Key key) 有语句 swim(qp[i]/index); 和 sink(qp[i]/index);what the earth happens?

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

Answer 1

这些是在更改密钥时需要执行的二进制堆上的操作。优先级队列中的每个 'node' 都保存在二进制堆中。当您添加一个项目时，该项目需要放置在正确的位置，因此 'rules of binary heap' 不会被破坏。

更改密钥时也会发生同样的情况，您需要更改项目在优先级堆中的位置，以免违反规则（该项目的子项不大于它，并且该项目的父项不小于） .

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

这个post只是对一个庞大而广泛的主题的介绍，我建议阅读更多相关内容（尤其是'heapify'部分）：check this out.

一般来说，重点是您只有一种更改键的方法，它会调用 swim 和 sink，因为前一个键可能更高或更低。它通常使用 2 个方法完成：decreaseKey 和 increaseKey，并且每个方法只调用一个 - sink 或 swim，因此。您的代码将这 2 个方法合并为 1 个，这就是它同时调用 sink 和 swim 的原因。当新密钥高于旧密钥时，意味着它需要在堆中上升（swim），当新密钥低于旧密钥时，它需要下降（sink） .

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

索引优先队列的困惑

The confusion of the index priority queue

java

algorithm

priority-queue