索引优先级队列混乱

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

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

我还想知道优先级队列和索引优先级队列之间的元素构造风格，以及索引优先级队列上的二进制堆中存储的内容?索引还是元素?

Answer 1

这些是在更改键时需要对二进制堆执行的操作。优先级队列中的每个"节点"都保存在二进制堆中。当你添加一个项目时，该项目需要被放置在正确的位置，所以"二进制堆的规则"不会被打破。

改变键也是一样，你需要改变项在优先级堆中的位置，这样规则才不会被打破(该项的子项不大于它，该项的父项不小于它)。

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

这篇文章只是一个巨大而广泛的主题的介绍，我建议阅读更多关于它的内容(特别是"heapify"部分):看看这个。

一般来说，关键是您只有一个方法来更改键，并且它调用swim和sink，因为前一个键可能更高或更低。它通常用2个方法完成:decreaseKey和increaseKey，每个方法只调用一个- sink或swim，相应地。您的代码将这两个方法组合为一个，这就是为什么它同时调用sink和swim。当新键比旧键高时，这意味着它需要在堆中向上移动(swim)，当新键比旧键低时，它需要向下移动(sink)。

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