0%

Java 堆与优先级队列(一):堆的概念和算法

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 中,有一个单独的内部类 EntryEntry 有三个引用,分别指向父节点、左孩子、右孩子。
    • 完全二叉树中,使用数组存储的优点是节省空间,而且访问效率高。
  • 完全二叉树 vs 排序二叉树

    • 在排序二叉树中,树是完全有序的,每个节点都有确定的前驱后继,而且不能有重复元素
    • 在堆中,可以有重复元素,元素间不是完全有序的,但对于父子节点之间,有一定的顺序要求

7. 什么是最大堆/最小堆

  • 根据堆中父子节点之间的顺序,分为两种堆:最大堆和最小堆。
  • 最大堆:每个节点都不大于其父节点,根节点是所有节点中最大的。
  • 最小堆:每个节点都不小于其父节点,根节点是所有节点中最小的。

8. 堆操作的主要算法的效率分别是

  • 添加删除元素时,有两个关键的过程以保持堆的性质,一个是向上调整(shiftup)、一个是向下调整(shiftdown),它们的效率(时间复杂度)都为 O(log2(N)) (N 为节点个数)
  • 无序数组构建堆的过程 heapify 是一个自底向上循环的过程,效率为 O(N)
  • 查找遍历就是对数组进行查找和遍历,效率为 O(N)
-------------------- 本文结束感谢您的阅读 --------------------