优先队列 #
- 有些情况下，不需要要求处理的元素全部有序，只要求每次都处理键值最大的元素，然后再收集更多的元素，然后再处理键值最大的元素
- 需要一种数据结构，支持操作：删除最大元素和插入元素，这种数据类型叫做优先队列
- 优先队列的基本表现形式：其一或两种操作都能在线性时间内完成
- 基于二叉堆数据结构的优先队列，用数组保存元素并按照一定条件排序，以实现高效的删除最大元素和插入元素
API #
抽象数据类型，最重要的操作是删除最大元素和插入元素 delMax()和insert()
用“最大元素”代替“最大键值”或是“键值最大的元素”
泛型优先队列的API
优先队列的调用示例 从N各输入中找到最大的M各元素所需成本
优先队列的用例 pq里面最多放5个，当大于5个的时候，就从中剔除1个
public class TopM { public static void main(String[] args) { // 打印输入流中最大的M行 int M = Integer.parseint(args[0]); MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1); while (StdIn.hasNextLine()) { // 为下一行输入创建一个元素并放入优先队列中 pq.insert(new Transaction(StdIn.readLine())); if (pq.size() > M) pq.delMin(); // 如果优先队列中存在M+1个元素则删除其中最小的元素 } // 最大的M个元素都在优先队列中 Stack<Transaction> stack = new Stack<Transaction>(); while (!pq.isEmpty()) stack.push(pq.delMin()); for (Transaction t : stack) StdOut.println(t); } }应用
初级实现 #
- 数组实现（无序） insert元素和栈的push()方法完全一样；要删除最大元素，可以添加一段类似选择排序的内循环的代码，将最大元素的边界元素交换，然后删除
- 数组实现（有序） insert()方法时，始终将较大的元素，向右边移动一格以使数组有序；删除最大元素就是pop()
- 链表表示法
- 可以用基于链表的下压栈的代码作为基础，而后可以选择修改pop() 来找到并返回最大元素，或是修改push() 来保证所有元素为逆序并用pop() 来删除并返回链表的首元素(也就是最大的元素)
- 优先队列的各种实现在最坏情况下运行时间的增长数量级
- 在一个优先队列上执行的一系列操作如表2.4.4所示
堆的定义 #
当一棵二叉树的每个节点都大于等于他的两个子结点时，它被称为堆有序
重要性质1
在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素
重要命题 根结点是堆有序的二叉树中的最大结点
二叉堆表示法
- 如果使用指针来表示堆有序的二叉树，需要三个指针来找到它的上下结点
- 使用数组来表示(前提是使用完全二叉树来表示)，那么只要一层一层由上向下从左至右，在每个结点的下方连接两个更小的结点，直至将N个结点全部连接完毕 即将二叉树的结点按照层级顺序放入数组中
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使 用数组的第一个位置）
图解
下面将二叉树 简称为堆
在一个堆中，位置k 的结点的父结点的位置为k/2，而它的两个子结点的位置则分别为2k 和2k+1。这样在不使用指针的情况下（我们在第3 章中讨论二叉树时会用到它们）我们也可以通过计算数组的索引在树中上下移动：从a[k] 向上一层就令k 等于k/2，向下一层则令k 等于2k 或2k+1
一棵大小为N的完全二叉树的高度为[lgN]
当N达到2的幂时树的高度为加1 数组不使用位置[0]
堆的算法 #
堆实现的比较和交换方法
private Boolean less(int i, int j) { return pq[i].compareTo(pq[j]) < 0; } private void exch(int i, int j) { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }堆的操作首先进行一些简单的改动，打破堆的状态，再遍历堆并按照要求将堆的状态回复，这个过程称为堆的有序化
当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序
由下至上的堆有序化（上浮）【在最后位置插入一个元素】
说明 如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。交换后，这个结点比它的两个子结点都大（一个是曾经的父结点，另一个比它更小，因为它是曾经父结点的子结点），但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇 到了一个更大的父结点。
代码
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; //j<N用来判断j是否存在右兄弟结点，当j==N（即j为树的[从左到右]最末一个结点，那么它没有右兄弟结点） if (j < N && less(j, j+1)) j++; //当根节点没有小于子节点时，跳出循环 if (!less(k, j)) break; exch(k, j); k = j; } }
对于上面的说明
- 插入元素。我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位 置（如图2.4.5 左半部分所示）。
- 删除最大元素。我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减 小堆的大小并让这个元素下沉到合适的位置（如图2.4.5 右半部分所示）
- 上面对优先队列API的实现，能够保证插入元素和删除元素这两个操作的用时，和队列的大小仅成对数关系
图解堆的操作
基于堆的优先队列
public class MaxPQ<Key extends Comparable<Key>> { private Key[] pq; // 基于堆的完全二叉树 private int N = 0; // 存储于pq[1..N]中，pq[0]没有使用 public 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]; // 从根结点得到最大元素 exch(1, N--); // 将其和最后一个结点交换 pq[N+1] = null; // 防止对象游离 sink(1); // 恢复堆的有序性 return max; } // 辅助方法的实现请见本节前面的代码框 private Boolean less(int i, int j) private void exch(int i, int j) private void swim(int k) private void sink(int k) }说明
优先队列由一个基于堆的完全二叉树表示， 存储于数组pq[1..N] 中，pq[0] 没有使用。在insert() 中，我们将N 加一并把新元素添加在数组最后，然后用swim() 恢复堆的秩序。在delMax() 中，我们从pq[1] 中得到需要返回的元素，然后将pq[N] 移动到pq[1]，将N 减一并用sink() 恢复堆的秩序。同时我们还将不再使用的pq[N+1] 设为null，以便系统回收它所占用的空间。和以前一样（请见1.3 节），这里省略了动态调整数组大小的代码
对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN+1）次比较，删除最大元素的操作需要不超过2lgN 次比较。
在堆上进行操作
多叉堆 基于用数组表示的完全三叉树构造堆并修改相应的代码并不困难。对于数组中1 至N 的N 个元素，位置k的结点大于等于位于3k-1、3k 和3k+1 的结点，小于等于位于(k+1)/3 的结点
调整数组大小 添加一个没有参数的构造函数， 在insert() 中添加将数组长度加倍的代码，在delMax()中添加将数组长度减半的代码，就像在1.3 节中的栈那样
元素的不可变性 优先队列存储了用例创建的对象，但同时假设用例代码不会改变它们
索引优先队列 注意minIndex()，最小元素的索引不一定是0，这里说的索引不是IndexMinPQ数据结构中的数组的索引。这两个不是一个意思
- 表2.4.6 含有N 个元素的基于堆的索引优先队列所有操作在最坏情况下的成本
索引优先队列用例 将多个有序的输入流归并成一个有序的输出流 ★注意，这多个输入流本身是有序的
public class Multiway { public static void merge(In[] streams) { int N = streams.length; IndexMinPQ<String> pq = new IndexMinPQ<String>(N); for (int i = 0; i < N; i++){ if (!streams[i].isEmpty()){ //初始化，从文件流中读取一个数，放到优先队列中 pq.insert(i, streams[i].readString()); } } while (!pq.isEmpty()) { StdOut.println(pq.min()); //从优先队列中取最小的数出来 int i = pq.delMin(); if (!streams[i].isEmpty()) //取出数的那个位置，再从文件流读一个值放进去 pq.insert(i, streams[i].readString()); } } public static void main(String[] args) { int N = args.length; In[] streams = new In[N]; for (int i = 0; i < N; i++) streams[i] = new In(args[i]); //三个文件地址 merge(streams); } }
堆排序 #
我们可以把任意优先队列变成一种排序方法，将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将他们按顺序删去
- 用堆来实现经典而优雅的排序算法–堆排序
- 为了与前面代码保持一致，使用面向最大元素的优先队列并重复删除最大元素；为了排序需要，直接使用swim()和sink()，且将需要排序的数组本身作为堆，省去额外空间
堆的构造
可以从左到右，就像连续向优先队列中插入元素一样
从右到左，用sink()函数构造子堆
★ 重要前提：每个子堆都符合优先序列的根节点大于其他两个子节点（也就是我们可以跳过大小为1的子堆） 所以只要对每个子堆的根节点，进行sink()函数操作就可以构造出优先队列结构的数组了
进行排序 主要是将数组的位置1和N-1进行交换，然后在1位置进行sink()操作 不断循环，即可让整个数组有序
sort(Comparable[] a) { int N = a.length; for (int k = N/2; k >= 1; k--) sink(a, k, N); while (N > 1) { exch(a, 1, N--); sink(a, 1, N); } }- 注意，这里的sink()函数被修改过，主要是指定了要sink的最后一个位置【sink() 被修改过，以a[] 和N 作为参数】
堆排序的轨迹（每次下沉后的数组内容）
堆排序：堆的构造（左）和下沉排序（右）
堆排序的主要工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小 后数组中空出的位置
将N个元素排序，堆排序只需少于（2N x lgN+2N ）次比较（以及一般次数的交换）
。2N 项来自于堆的构造（ 见命题R）。2NlgN 项来自于每次下沉操作最大可能需要2lgN次比较（见命题P 与命题Q）
我们将该实现和优先队列的API 独立开来是为了突出这个排序算法的简洁性（sort() 方法只需8 行代码，sink() 函数8 行），并使其可以嵌入其他代码之中。
小结
- 在最坏的情况下它也能保证使用～ 2NlgN 次比较和恒定的额外空间。当空间十分紧张的时候（例如在嵌入式系统或低成本的移动设备中）它很流行，因为它只用几行就能实现（甚至机器码也是）较好的性能。但现代系统的许多应用很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序、归并排序，甚至是希尔排序
- 用堆实现的优先队列在现代应用程序中越来越重要，因为它能在插入操作和删除最大元素操作混合的动态场景中保证对数级别的运行时间