Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 谢路云
Chapter 2 Section 4 优先队列

优先队列

优先队列API

N个数找到最大M个元素的时间成本

时间成本

不同数据结构下的时间成本

时间成本

堆

堆的定义

定义：当一棵二叉树的每个结点都大于等于它的两个子节点时，它称为堆有序

相应地，在堆有序的二叉树中，每个结点都小于等于它的父节点。从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素。特别的：根结点是堆有序的二叉树中的最大结点。

二叉堆表示法

二叉堆：就是堆有序的完全二叉树，元素在数组中按照层级存储（一层一层的放入数组中，不用数组的第一个元素，因为0*2=0，递推关系不合适）。下面简称堆。

堆中：位置K的结点的父节点的位置为 ⌊k/2⌋ ，子节点的位置分别是 2k 和 2k+1

一个结论：一棵大小为N的完全二叉树的高度为 ⌊lgN⌋

二叉堆表示法

用数组（堆）实现的完全二叉树是很严格的，但它的灵活性足以使我们高效地实现优先队列。

堆的算法

我们用数组pq[N+1]来表示大小为N的堆，我们不使用pq[0]。

上浮（由下至上的堆有序）

private void swim(int k) {while (k > 1 && less(k / 2, k)) {exch(k / 2, k);k = k / 2;}
}

下沉（由上至下的堆有序）

private void sink(int k) {while (2 * k <= N) {int j = 2 * k;if (j < N && less(j, j + 1)) j++; //找到子节点中更大的那个if (!less(k, j)) break; //如果父结点比较大，则终止exch(k, j);//如果父结点比较小，则把子节点中更大的那个jiaohuanshanglaik = j;}
}

MaxPQ 代码

复杂度
- 插入：不超过lgN+1次比较
- 删除最大元素：不超过2lgN次比较

简易版

public class MaxPQ<Key extends Comparable<Key>> {private Key[] pq; // heap-ordered complete binary treeprivate int N = 0; // in pq[1..N] with pq[0] unusedpublic MaxPQ(int maxN) {pq = (Key[]) new Comparable[maxN + 1];}public boolean isEmpty() {return N == 0;}public int size() {return N;}public void insert(Key v) {pq[++N] = v; //添加到最后swim(N); //上浮}public Key delMax() {Key max = pq[1]; // Retrieve max key from top.最大的为根结点exch(1, N--); // Exchange with last item.和最后一个结点交换，并减小Npq[N + 1] = null; // Avoid loitering.删除原来的最后一位sink(1); // Restore heap property.下沉return max;}// See aboveprivate boolean less(int i, int j)private void exch(int i, int j)    private void swim(int k)    private void sink(int k)
}

完整版

添加resize功能

public class MaxPQ<Key> implements Iterable<Key> {private Key[] pq;                    // store items at indices 1 to Nprivate int N;                       // number of items on priority queueprivate Comparator<Key> comparator;  // optional Comparatorpublic MaxPQ(int initCapacity) {pq = (Key[]) new Object[initCapacity + 1];N = 0;}public MaxPQ() {this(1);}public MaxPQ(int initCapacity, Comparator<Key> comparator) {this.comparator = comparator;pq = (Key[]) new Object[initCapacity + 1];N = 0;}public MaxPQ(Comparator<Key> comparator) {this(1, comparator);}public MaxPQ(Key[] keys) {N = keys.length;pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < N; i++)pq[i+1] = keys[i];for (int k = N/2; k >= 1; k--)sink(k);assert isMaxHeap();}public boolean isEmpty() {return N == 0;}public int size() {return N;}public Key max() {if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");return pq[1];}// helper function to double the size of the heap arrayprivate void resize(int capacity) {assert capacity > N;Key[] temp = (Key[]) new Object[capacity];for (int i = 1; i <= N; i++) {temp[i] = pq[i];}pq = temp;}public void insert(Key x) {// double size of array if necessaryif (N >= pq.length - 1) resize(2 * pq.length);// add x, and percolate it up to maintain heap invariantpq[++N] = x;swim(N);assert isMaxHeap();}public Key delMax() {if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");Key max = pq[1];exch(1, N--);sink(1);pq[N+1] = null;     // to avoid loiterig and help with garbage collectionif ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);assert isMaxHeap();return max;}private void swim(int k) {while (k > 1 && less(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 && less(j, j+1)) j++;if (!less(k, j)) break;exch(k, j);k = j;}}private boolean less(int i, int j) {if (comparator == null) {return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;}else {return comparator.compare(pq[i], pq[j]) < 0;}}private void exch(int i, int j) {Key swap = pq[i];pq[i] = pq[j];pq[j] = swap;}// is pq[1..N] a max heap?private boolean isMaxHeap() {return isMaxHeap(1);}// is subtree of pq[1..N] rooted at k a max heap?private boolean isMaxHeap(int k) {if (k > N) return true;int left = 2*k, right = 2*k + 1;if (left  <= N && less(k, left))  return false;if (right <= N && less(k, right)) return false;return isMaxHeap(left) && isMaxHeap(right);}public Iterator<Key> iterator() {return new HeapIterator();}private class HeapIterator implements Iterator<Key> {// create a new pqprivate MaxPQ<Key> copy;// add all items to copy of heap// takes linear time since already in heap order so no keys movepublic HeapIterator() {if (comparator == null) copy = new MaxPQ<Key>(size());else                    copy = new MaxPQ<Key>(size(), comparator);for (int i = 1; i <= N; i++)copy.insert(pq[i]);}public boolean hasNext()  { return !copy.isEmpty();                     }public void remove()      { throw new UnsupportedOperationException();  }public Key next() {if (!hasNext()) throw new NoSuchElementException();return copy.delMax();}}public static void main(String[] args) {MaxPQ<String> pq = new MaxPQ<String>();while (!StdIn.isEmpty()) {String item = StdIn.readString();if (!item.equals("-")) pq.insert(item);else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");}StdOut.println("(" + pq.size() + " left on pq)");}}

索引优先队列

增加索引
增加change, contains, delete方法

索引优先队列API

索引优先队列

各方法的时间成本

IndexMinPQ 代码

简易版

public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {private int maxN;        // maximum number of elements on PQprivate int N;           // number of elements on PQprivate int[] pq;        // binary heap using 1-based indexingprivate int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = iprivate Key[] keys;      // keys[i] = priority of ipublic IndexMinPQ(int maxN) {this.maxN = maxN;keys = (Key[]) new Comparable[maxN + 1];    // 存一发原来的数组pq   = new int[maxN + 1];    // 这是二叉树，比如1位置放的是想要记录的是keys[3]，但是记录了3，即pq[1]=3qp   = new int[maxN + 1];    // 反过来，keys[3]放在哪里了呢？放在了树的1位置, qp[3]=1for (int i = 0; i <= maxN; i++)qp[i] = -1;}public void insert(int i, Key key) {if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");N++;qp[i] = N; // i放到了树最后的位置N，通过原数组i找到树中的位置Npq[N] = i; // 树的最后位置N放了i，通过树中的位置N找到原数组ikeys[i] = key; //具体是什么swim(N); //上浮}private void swim(int k)  {while (k > 1 && greater(k/2, k)) {exch(k, k/2); //在这里pq,qp都换好了k = k/2;}}private void exch(int i, int j) {int swap = pq[i];pq[i] = pq[j];pq[j] = swap;qp[pq[i]] = i; //因为是逆运算qp[pq[j]] = j;}    public int delMin() { if (N == 0) throw new NoSuchElementException("Priority queue underflow");int min = pq[1];        exch(1, N--); sink(1);qp[min] = -1;        // deletekeys[min] = null;    // to help with garbage collectionpq[N+1] = -1;        // not neededreturn min; }public void changeKey(int i, Key key) {//改的是原来的数组if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");keys[i] = key;swim(qp[i]); //可能往上sink(qp[i]); //可能往下}  
}

完整版

public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {private int maxN;        // maximum number of elements on PQprivate int N;           // number of elements on PQprivate int[] pq;        // binary heap using 1-based indexingprivate int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = iprivate Key[] keys;      // keys[i] = priority of ipublic IndexMinPQ(int maxN) {if (maxN < 0) throw new IllegalArgumentException();this.maxN = maxN;keys = (Key[]) new Comparable[maxN + 1];   pq   = new int[maxN + 1];qp   = new int[maxN + 1];                   for (int i = 0; i <= maxN; i++)qp[i] = -1;}public boolean isEmpty() {return N == 0;}public boolean contains(int i) {if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();return qp[i] != -1;}public int size() {return N;}public void insert(int i, Key key) {if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");N++;qp[i] = N;pq[N] = i;keys[i] = key;swim(N);}public int minIndex() { if (N == 0) throw new NoSuchElementException("Priority queue underflow");return pq[1];        }public Key minKey() { if (N == 0) throw new NoSuchElementException("Priority queue underflow");return keys[pq[1]];        }public int delMin() { if (N == 0) throw new NoSuchElementException("Priority queue underflow");int min = pq[1];        exch(1, N--); sink(1);assert min == pq[N+1];qp[min] = -1;        // deletekeys[min] = null;    // to help with garbage collectionpq[N+1] = -1;        // not neededreturn min; }public Key keyOf(int i) {if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");else return keys[i];}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 change(int i, Key key) {changeKey(i, key);}public void decreaseKey(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");if (keys[i].compareTo(key) <= 0)throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");keys[i] = key;swim(qp[i]);}public void increaseKey(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");if (keys[i].compareTo(key) >= 0)throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");keys[i] = key;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 boolean greater(int i, int j) {return keys[pq[i]].compareTo(keys[pq[j]]) > 0;}private void exch(int i, int j) {int swap = pq[i];pq[i] = pq[j];pq[j] = swap;qp[pq[i]] = i;qp[pq[j]] = j;}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;}}public Iterator<Integer> iterator() { return new HeapIterator(); }private class HeapIterator implements Iterator<Integer> {// create a new pqprivate IndexMinPQ<Key> copy;// add all elements to copy of heap// takes linear time since already in heap order so no keys movepublic HeapIterator() {copy = new IndexMinPQ<Key>(pq.length - 1);for (int i = 1; i <= N; i++)copy.insert(pq[i], keys[pq[i]]);}public boolean hasNext()  { return !copy.isEmpty();                     }public void remove()      { throw new UnsupportedOperationException();  }public Integer next() {if (!hasNext()) throw new NoSuchElementException();return copy.delMin();}}
}