用最通俗的语言和漫画来介绍二叉堆

优雅的算法 TOMORROW 来源:程序员小灰 3个月前 (09-22) 148次浏览 0个评论 扫描二维码

二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。下面通过一组漫画幽默风趣、通俗易懂地介绍二叉堆的定义以及基本操作(插入、删除等)。

用最通俗的语言和漫画来介绍二叉堆

 

用最通俗的语言和漫画来介绍二叉堆

—————  第二天  —————

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

————————————

 

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

什么是二叉堆

二叉堆本质上是一种完全二叉树,它分为两个类型:

1.最大堆

2.最小堆

什么是最大堆呢?最大堆任何一个父节点的值,都大于等于它左右孩子节点的值。

用最通俗的语言和漫画来介绍二叉堆

什么是最小堆呢?最小堆任何一个父节点的值,都小于等于它左右孩子节点的值。

用最通俗的语言和漫画来介绍二叉堆

二叉堆的根节点叫做堆顶

最大堆和最小堆的特点,决定了在最大堆的堆顶是整个堆中的最大元素;最小堆的堆顶是整个堆中的最小元素

用最通俗的语言和漫画来介绍二叉堆

堆的自我调整

对于二叉堆,如下有几种操作:

插入节点

删除节点

构建二叉堆

这几种操作都是基于堆的自我调整。

下面让我们以最小堆为例,看一看二叉堆是如何进行自我调整的。

1.插入节点

二叉堆的节点插入,插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点,值是 0。

用最通俗的语言和漫画来介绍二叉堆

这时候,我们让节点 0 的它的父节点 5 做比较,如果 0 小于 5,则让新节点“上浮”,和父节点交换位置。

 

用最通俗的语言和漫画来介绍二叉堆

继续用节点 0 和父节点 3 做比较,如果 0 小于 3,则让新节点继续“上浮”。

 

用最通俗的语言和漫画来介绍二叉堆

继续比较,最终让新节点 0 上浮到了堆顶位置。

用最通俗的语言和漫画来介绍二叉堆

2.删除节点

二叉堆的节点删除过程和插入过程正好相反,所删除的是处于堆顶的节点。比如我们删除最小堆的堆顶节点 1。

 

用最通俗的语言和漫画来介绍二叉堆

这时候,为了维持完全二叉树的结构,我们把堆的最后一个节点 10 补到原本堆顶的位置。

用最通俗的语言和漫画来介绍二叉堆

接下来我们让移动到堆顶的节点 10 和它的左右孩子进行比较,如果左右孩子中最小的一个(显然是节点 2)比节点 10 小,那么让节点 10“下沉”。

用最通俗的语言和漫画来介绍二叉堆

继续让节点 10 和它的左右孩子做比较,左右孩子中最小的是节点 7,由于 10 大于 7,让节点 10 继续“下沉”。

用最通俗的语言和漫画来介绍二叉堆

这样一来,二叉堆重新得到了调整。

3.构建二叉堆

构建二叉堆,也就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有非叶子节点依次下沉

我们举一个无序完全二叉树的例子:

用最通俗的语言和漫画来介绍二叉堆

首先,我们从最后一个非叶子节点开始,也就是从节点 10 开始。如果节点 10 大于它左右孩子中最小的一个,则节点 10 下沉。

用最通俗的语言和漫画来介绍二叉堆

接下来轮到节点 3,如果节点 3 大于它左右孩子中最小的一个,则节点 3 下沉。

用最通俗的语言和漫画来介绍二叉堆

接下来轮到节点 1,如果节点 1 大于它左右孩子中最小的一个,则节点 1 下沉。事实上节点 1 小于它的左右孩子,所以不用改变。

接下来轮到节点 7,如果节点 7 大于它左右孩子中最小的一个,则节点 7 下沉。

用最通俗的语言和漫画来介绍二叉堆

节点 7 继续比较,继续下沉。

用最通俗的语言和漫画来介绍二叉堆

这样一来,一颗无序的完全二叉树就构建成了一个最小堆。

用最通俗的语言和漫画来介绍二叉堆

堆的代码实现

在撸代码之前,我们还需要明确一点:

二叉堆虽然是一颗完全二叉树,但它的存储方式并不是链式存储,而是顺序存储。换句话说,二叉堆的所有节点都存储在数组当中。

用最通俗的语言和漫画来介绍二叉堆

数组中,在没有左右指针的情况下,如何定位到一个父节点的左孩子和右孩子呢?

像图中那样,我们可以依靠数组下标来计算。

假设父节点的下标是 parent,那么它的左孩子下标就是 2*parent+1;它的右孩子下标就是  2*parent+2 

比如上面例子中,节点 6 包含 9 和 10 两个孩子,节点 6 在数组中的下标是 3,节点 9 在数组中的下标是 7,节点 10 在数组中的下标是 8。

7 = 3*2+1

8 = 3*2+2

刚好符合规律。

有了这个前提,下面的代码就更好理解了:

public class HeapOperator {

  1. /**
  2. * 上浮调整
  3. * @param array     待调整的堆
  4. */
  5. public static void upAdjust(int[] array) {
  6.    int childIndex = array.length-1;
  7.    int parentIndex = (childIndex-1)/2;
  8.    // temp 保存插入的叶子节点值,用于最后的赋值
  9.    int temp = array[childIndex];
  10.    while (childIndex > 0 && temp < array[parentIndex])
  11.    {
  12.        //无需真正交换,单向赋值即可
  13.        array[childIndex] = array[parentIndex];
  14.        childIndex = parentIndex;
  15.        parentIndex = (parentIndex-1) / 2;
  16.    }
  17.    array[childIndex] = temp;
  18. }
  19.  
  20. /**
  21. * 下沉调整
  22. * @param array     待调整的堆
  23. * @param parentIndex    要下沉的父节点
  24. * @param parentIndex    堆的有效大小
  25. */
  26. public static void downAdjust(int[] array, int parentIndex, int length) {
  27.    // temp 保存父节点值,用于最后的赋值
  28.    int temp = array[parentIndex];
  29.    int childIndex = 2 * parentIndex + 1;
  30.    while (childIndex < length) {
  31.        // 如果有右孩子,且右孩子小于左孩子的值,则定位到右孩子
  32.        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
  33.            childIndex++;
  34.        }
  35.        // 如果父节点小于任何一个孩子的值,直接跳出
  36.        if (temp <= array[childIndex])
  37.            break;
  38.        //无需真正交换,单向赋值即可
  39.        array[parentIndex] = array[childIndex];
  40.        parentIndex = childIndex;
  41.        childIndex = 2 * childIndex + 1;
  42.    }
  43.    array[parentIndex] = temp;
  44. }
  45.  
  46. /**
  47. * 构建堆
  48. * @param array     待调整的堆
  49. */
  50. public static void buildHeap(int[] array) {
  51.    // 从最后一个非叶子节点开始,依次下沉调整
  52.    for (int i = array.length / 2; i >= 0; i--) {
  53.        downAdjust(array, i, array.length - 1);
  54.    }
  55. }
  56.  
  57. public static void main(String[] args) {
  58.    int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
  59.    upAdjust(array);
  60.    System.out.println(Arrays.toString(array));
  61.    array = new int[] {7,1,3,10,5,2,8,9,6};
  62.    buildHeap(array);
  63.    System.out.println(Arrays.toString(array));
  64. }

}

代码中有一个优化的点,就是父节点和孩子节点做连续交换时,并不一定要真的交换,只需要先把交换一方的值存入 temp 变量,做单向覆盖,循环结束后,再把 temp 的值存入交换后的最终位置。

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

用最通俗的语言和漫画来介绍二叉堆

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:用最通俗的语言和漫画来介绍二叉堆
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
优美的蜗牛发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到