image

编辑人: 独留清风醉

2024-10-16

0

815

最大堆_最小堆

分析&回答

堆的定义

堆树的定义是:n个元素的序列{k1,k2,…,kn},当且仅当满足如下关系时被成为堆树:

  • 堆树是一颗完全二叉树;
  • 堆树中某个节点的值总是不大于或不小于其孩子节点的值;
  • 堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示,左边为最大堆,右边为最小堆。

  • 最小堆:(1)Ki <= k2i 且 ki <= k2i-1  (i = 1,2,…[n/2])
  • 最大堆:(2)Ki >= k2i 且 ki >= k2i-1  (i = 1,2,…[n/2])

image-1691386124760

堆的输出 (以最小堆为例)

 

image-1691386134268

图1为一个最小堆,当最小节点根节点13输出后,将最后一个节点97作为根节点,移到顶端,如图2. 然后要对堆进行调整。比较此完全树的根节点与其两个子节点大小,因为27 < 38 < 97,所以27是三个节点里最小的,将节点27与根节点97交换。此时以97替代27而产生的右子树为一个新的堆,再以97为根节点,对此最小堆进行调整,同理,知道要将97与49交换,得到图3的完全树。此时以97代替49为根节点的右子树为一个新堆,再对此堆做同样的操作,因为此完全树已经是最小堆,所以可以停止操作,堆的调整完毕。此时再将根节点,对的最小值输出,并进行同样的调整,可以得到如图4的新堆。这个过程被称为“筛选”。

 #### 堆的初始化 (以最小堆为例)

从一个无序序列初始化为一个堆的过程就是一个反复“筛选”的过程。由完全二叉树的性质可以知,一个有n个节点的完全二叉树的最后一个非叶节点是节点[n/2],堆的初始化过程就从这个[n/2]节点开始。下图为如下无序数组的初始化:{49,38,65,97,76,13,27,50}

image-1691386146591

首先,未处理的数组对应的堆为图1模样。从第四个节点开始([8/2]=4),因为50 < 97,故要交换两节点,交换后还要继续对其新的左子树进行类似输出后那样的筛选。易见其左子树只有节点97,已经为最佳情况,故可以继续堆的初始化,如图2。再考虑第三个节点,因为13 < 27 < 65,即节点13为当前的最小节点,故与节点65交换,并对新的左子树进行筛选,其也为最佳情况,故可继续堆的初始化,结果如图3。然后考虑第二个节点,因为38 < 50 < 76,故已经为最优情况,不用调整。最后再考虑第一个节点,根节点。因为 13 < 38 < 49,故需要将根节点49与其右孩子节点13交换,交换后还要继续对其新的右子树进行类似输出后那样的筛选,可见右子树还需要调整,因为 27 < 49 < 65,故将节点49与节点27交换。此时已经处理完了根节点,初始化结束。最终结果如图5.

反思&扩展

构建好的最大堆或最小堆都不是排序好的,如果需要排序还需要继续处理。深入了解可以看Java版堆排序


喵呜面试助手: 一站式解决面试问题,你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享!

创作类型:
原创

本文链接:最大堆_最小堆

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章