索引优先级队列的混淆

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'部分):检查一下.

一般来说,问题是你只有1改变的关键方法,它调用既swim和sink,因为以前的钥匙可能会更高或更低.它通常用2种方法完成:decreaseKey和increaseKey,并且每个方法只调用一个 - sink或者swim相应地.你的代码将这2个方法组合成1,这就是为什么它同时调用sink和swim.当新密钥高于旧密钥时,这意味着它需要在堆(swim)中上升,当新密钥低于旧密钥时,它需要向下(sink).

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