读《算法与数据结构》第六、七、八、九章

一、堆

二、大根堆和小根堆

1、大根堆
（1）每个子二叉树的根均大于等于其左、右子结点，在堆中，根结点是最大结点

2、小根堆
（1）每个子二叉树的根均小于等于左、右子结点，在堆中，根结点是最小结点

三、优先队列

1、优先队列
（1）最小元素先出
（2）常见的抽象数据类型
（3）用小根堆表示优先队列

2、时间复杂度
（1）删除时，对每层最多只需要做2次比较，而循环是从树根到树叶进行的，负复杂度O(logn)
（2）取出最小元素的时间代价为O(1)

四、哈夫曼算法及其应用

1、示例


2、二路归并排序
（1）两两合并
（2）按照哈夫曼树的结构从外部结点到根结点逐层进行合并，一定是一种最佳（但并非唯一的）合并顺序

五、集合及其抽象数据类型

1、位向量
（1）每个元素都是二进制位的数组

2、字典
（1）每个元素都有两部分组成，即关键码和属性

3、二分法