第六章 优先队列(堆)
1. 基本概念
一种特殊的队列，至少支持两种操作：Insert和DeleteMin；前者插入元素，相当于队列的enqueue,后者查找、删除、返回最小的元素，相当于队列的dequeue。
2. 二叉堆
概念
具有结构性质和堆序性质的二叉树（或者说具有堆序性质的完全二叉树）
性质
- 结构性质：完全二叉树
- 堆序性质：父节点小于任意子节点
实现方法
数组即可， 鉴于其完全二叉树的性质，乘以2可以到达左子节点，除以2可以到达父节点。
操作及其时间复杂度：（后面四种操作需要节点位置信息为基础）
- Insert: 采用上滤，最坏为O(logN)，平均只要比较2.607次，上移1.607层，O（1）
- DeleteMin: 采用下滤，最坏为O(logN)，平均为O(logN)
- DecreaseKey:
- IncreaseKey:
- Delete:
- BuildHeap: 空堆N个Insert操作来完成，总运行时间O（N）
3. d堆
- 类似二叉堆，只是节点的儿子数都是d个（除了最底层的一些节点）。
- 有证据显示，4堆在实践中可以胜过二叉堆。
4.左式堆
概念
具有堆序性质和和零路径长相关的结构性质的二叉树。
性质
- 堆序性质：父节点小于任意子节点；
- 结构性质：左儿子节点的零路径长不小于右儿子节点的零路径长。（=>N个节点的左式堆右路径上节点不超过[log(N+1)]）
实现方法
采用二叉树的实现方法，每个节点增加零路径长域。
操作及其实践复杂度
- Merge：从由路径节点入手，O（logN)
- Insert：合并一个节点左式堆，O（logN)
- DeleteMin：O（logN)
5. 斜堆
概念
具有堆序的二叉树，但不具有结构性质；其基本操作Merge和左氏堆一致，但是右路径上的节点左右儿子的交换是无条件的（除了右路径上最大节点不交换其左右儿子）
操作
- Merge：任意单次操作最坏时间O（N），摊还时间O（logN）
- ...
6. 二项队列（binomial queue）
概念
具有堆序的二项树的集合（森林）。
操作
- Merge： O（logN）
- Insert：O（logN)；从空堆连续N次插入总最坏时间O（N）
- Delete：O（logN）
