1. 数据结构中的堆可以高效地解决哪些问题
- 优先级队列，队列实现类
LinkedList是按添加顺序排列的。但现实中，经常需要按优先级来，每次都应该处理当前队列中优先级最高的，高优先级的即使来得晚，也应该被优先处理 - 求前 K 个最大的元素，元素个数不确定，数据量可能很大，甚至源源不断到来，但需要知道到目前为止的最大的前 K 个元素。这个问题的变体有：求前 K 个最小的元素、求第 K 个最大的元素、求第 K 个最小的元素
- 求中值元素，中值不是平均值，而是排序后中间那个元素的值。同样，数据量可能很大，甚至源源不断到来
- 堆还可以实现排序，称之为堆排序，不过有比它更好的排序算法
2. 数据结构中的堆的概念是
- 堆首先是一颗二叉树，但它是完全二叉树
- 逻辑概念上，堆是完全二叉树，父子节点间有特定顺序，分为最大堆和最小堆。最大堆中根是最大的，最小堆中根是最小的
- 物理概念上，堆使用数组进行存储，元素索引有一定顺序要求
3. 什么是满二叉树和完全二叉树
满二叉树
- 除了最后一层外，每个节点都有两个孩子节点
- 最后一层都是叶子节点，都没有孩子节点
完全二叉树
- 满二叉树一定是完全二叉树，但完全二叉树不要求最后一层是满的
- 但如果不满，则要求所有节点必须集中在最左边，从左到右是连续的，中间不能有空的
4. 完全二叉树的特点是
- 在完全二叉树中，可以给每个节点一个编号，编号从 1 开始连续递增，从上到下，从左到右
- 给定任意一个节点，可以根据其编号直接快速计算出其父节点和孩子节点编号
- 如果编号为 i，则父节点编号即为 i/2
- 左孩子编号即为 2 * i，右孩子编号即为 2 * i + 1
5. 完全二叉树的物理存储方式是
- 逻辑概念上的二叉树可以方便地存储到数组中，数组中的元素索引就对应节点编号，树中的父子关系通过其索引关系隐含维持，不需要单独保持
- 堆逻辑概念上是一颗完全二叉树，而物理存储上使用数组，还有一定的顺序要求
6. 完全二叉树与 TreeMap、排序二叉树的区别分别是什么
完全二叉树 vs
TreeMap- 在
TreeMap中，有一个单独的内部类Entry，Entry有三个引用，分别指向父节点、左孩子、右孩子 - 完全二叉树中，使用数组存储的优点是节省空间，而且访问效率高
- 在
完全二叉树 vs 排序二叉树
- 在排序二叉树中，树是完全有序的，每个节点都有确定的前驱和后继，而且不能有重复元素
- 在堆中，可以有重复元素，元素间不是完全有序的，但对于父子节点之间，有一定的顺序要求
7. 什么是最大堆/最小堆
- 根据堆中父子节点之间的顺序，分为两种堆：最大堆和最小堆
- 最大堆：每个节点都不大于其父节点，根节点是所有节点中最大的
- 最小堆：每个节点都不小于其父节点，根节点是所有节点中最小的
8. 堆操作的主要算法的效率分别是
- 在添加和删除元素时，有两个关键的过程以保持堆的性质，一个是向上调整（shiftup)、一个是向下调整（shiftdown），它们的效率（时间复杂度）都为
O(log2(N))（N 为节点个数） - 由无序数组构建堆的过程 heapify 是一个自底向上循环的过程，效率为
O(N) - 查找和遍历就是对数组进行查找和遍历，效率为
O(N)