我已经得到了优先queue.But的想法，当涉及到索引优先级队列索引优先级队列

Question

的困惑，我的一些方法，如变化的FPGA实现（INT K A有点困惑， Item item） and delete（int i）。

变化（INT K，项项）是具有k相关联的项目改变为项目

删除（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 

我明白了接收器和游泳的操作。但是为什么在方法删除（int i）和chang eKey（int i，Key key）有语句swim(qp[i]/index);和sink(qp[i]/index);究竟发生了什么？

而且我也想知道优先级队列和索引优先级队列，什么之间的所有元素作风建设是存储在索引优先级队列？索引或元素的二叉堆？

Answer 1

这些都是，要执行的需要在堆操作，当你改变的关键。优先级队列中的每个“节点”都保存在堆中。当你添加一个项目时，这个项目需要被放置在一个正确的位置，所以'堆的规则'不会被破坏。改变密钥也是一样，你需要在堆中改变项目的位置，这样规则就不会被破坏（该项目的子项不会比它大，并且该项目的父项不会更小）。这个优先级队列是用二进制堆实现的，这意味着它是基于二叉树的，这就是为什么你可以在这些方法中看到2除法的原因，因为它需要一层一层地进行项上/下，并且通过该部分来实现第一级有一个节点，第二级有两个节点，第三级有四个节点等等，节点数量是每个级别乘以2）。这篇文章只是介绍了一个巨大而广泛的话题，我建议您阅读更多关于它（尤其是“heapify”部分）：check this out.

一般情况下，关键是你有改变的关键只有1种方法，它调用这两个swim和sink，因为之前的密钥可能更高或更低。它通常用两种方法完成：decreaseKey和increaseKey，每个这些方法调用只有一个 - sink或swim，相应地。您的代码将这两种方法合并为1，这就是为什么它调用sink和swim。当新的关键是比旧钥匙，这意味着它需要在堆（swim），当新的关键是比它需要往下走旧密钥（sink）低上去更高。

btw。我的整篇文章假设我们正在处理最大的堆 - 这意味着根节点具有最大值，而他的子节点的值更小等。还有一个最小堆，它是完全相反的。