【数据结构与算法】系列二十一 - 优先级队列和哈夫曼树

。。。

一、优先级队列

优先级队列（Priority Queue）也是个队列，因此也是提供和队列一样的接口。在实际开发中应用十分广泛，例如下面的两个场景。

场景一：医院的夜间门诊，队列元素是病人，优先级是病情的严重情况、挂号时间。

场景二：操作系统的多任务调度，队列元素是任务，优先级是任务类型。

1.1. 接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空 
void enQueue(E element); // 入队 
E deQueue(); // 出队
E front(); // 获取队列的头元素 
void clear(); // 清空

普通的队列是FIFO（先进先出）原则，优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队。

1.2. 底层实现

根据优先队列的特点，很容易想到：可以直接利用二叉堆作为优先队列的底层实现。可以通过Comparator或Comparable去自定义优先级高低。

public class PriorityQueue<E> {
  private BinaryHeap<E> heap;

  public PriorityQueue(Comparator<E> comparator) {
    heap = new BinaryHeap<>(comparator);
  }

  public PriorityQueue() {
    this(null);
  }

  public int size() {
    return heap.size();
  }

  public boolean isEmpty() {
    return heap.isEmpty();
  }

  public void clear() {
    heap.clear();
  }

  public void enQueue(E element) {
    heap.add(element);
  }

  public E deQueue() {
    return heap.remove();
  }

  public E front() {
    return heap.get();
  }
}

Java官方的优先级队列就是用二叉堆实现的。参考java.util.PriorityQueue。

二、哈夫曼树和哈夫曼编码

哈夫曼编码（Huffman Coding），又称为霍夫曼编码，它是现代压缩算法的基础。

假设要把字符串ABBBCCCCCCCCDDDDDDEE转成二进制编码进行传输，可以转成ASCII编码（65 ~ 69，二进制是1000001 ~ 1000101，按照7位一组进行解析），但是这种编码方式有点冗长，如果希望编码更短怎么操作呢？

可以先约定5个字母对应的二进制：

对应的二进制编码：000001001001010010010010010010010010011011011011011011100100，一共20个字母，转成了60个二进制位。

如果使用哈夫曼编码，可以压缩至41个二进制位，约为原来长度的68.3%。

在了解哈夫曼编码之前，我们先看下什么是哈夫曼树。

2.1. 哈夫曼树

如上面案例，先计算出每个字母的出现频率（权值，这里直接用出现次数）：

利用这些权值，构建一棵哈夫曼树（又称为霍夫曼树、最优二叉树）。

如何构建一棵哈夫曼树？（假设有n个权值）

第一步：以权值作为根节点构建n棵二叉树，组成森林。

第二步：在森林中选出2个根节点最小的树合并，作为一棵新树的左右子树，且新树的根节点为其左右子树根节点之和。

第三步：从森林中删除刚才选取的2棵树，并将新树加入森林。

第四步：重复第二步和第三步，直到森林只剩一棵树为止，该树即为哈夫曼树。

2.2. 哈夫曼编码

根据最终得到的哈夫曼树，left为0，right为1，可以得出5个字母对应的哈夫曼编码：

ABBBCCCCCCCCDDDDDDEE的哈夫曼编码是1110110110110000000001010101010101111。

可以看出，元素都是出现在叶子节点上，每一个哈夫曼编码都是一个叶子节点的路径。

总结：

• n个权值构建出来的哈夫曼树拥有n个叶子节点
• 每个哈夫曼编码都不是另一个哈夫曼编码的前缀
• 哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近
  • 带权路径长度：树中所有的叶子节点的权值乘上其到根节点的路径长度。与最终的哈夫曼编码总长度成正比关系（哈夫曼编码总长 = 路径长度 * 权值）。