索引优先队列的混淆问题

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

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

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

- FrancisGeek

---

IndexPrioriryQueue（或者你的类名）不是一个标准类。能否分享一下这个类的其余代码？或者你使用的API的名称？ - undefined

@Asoub 这段code似乎来自Algorithms这本书。 - undefined

离题一点，我认为bubbleUp和bubbleDown比swim和sink更好。 - undefined

Answer 1

这些是在更改键时需要执行的二叉堆操作。优先队列中的每个“节点”都保留在二叉堆中。添加项目时，该项需要定位到正确的位置，以便不违反“二叉堆规则”。

更改键时也会发生同样的情况，您需要更改优先级堆中该项的位置，以便不违反规则（该项的子项不比它大，并且该项的父项不小）。

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

本文只是一个庞大而广泛的主题的介绍，建议阅读更多相关内容（特别是“heapify”部分）：查看这里。

通常情况下，更改键的唯一方法是调用 swim 和 sink 两个方法，因为先前的键可能较高或较低。通常使用两种方法：decreaseKey 和 increaseKey，每个方法只调用其中一个 - sink 或 swim。您的代码将这两种方法合并为一种，因此它会调用 sink 和 swim。当新键高于旧键时，它需要在堆中向上移动（swim），当新键低于旧键时，它需要向下移动（sink）。

顺便说一句，我整篇文章都假定我们正在使用最大堆 - 这意味着根节点具有最大值，其子节点具有较小的值等。还有一种最小堆，它是完全相反的。

- Shadov