数据结构-堆

 我来答
黑科技1718
2022-06-08 · TA获得超过5880个赞
知道小有建树答主
回答量:433
采纳率:97%
帮助的人:82.1万
展开全部

堆其实就是一棵完全二叉树,即若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。

定义为:具有n个元素的序列(h1,h2,...hn),当且仅当满足(hi>=h2i,hi>=h2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。完全二叉树的根结点称为堆的顶。

可以注意到,堆仅保证元素和其子结点之间的关系,并不保证兄弟结点之间的关系。

常见的堆包括最大堆和最小堆。

最大堆,顾名思义,堆顶的键值是所有堆结点键值中最大者。套用前面讲到过的规则, 当且仅当满足(hi>=h2i,hi>=h2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2) ,所有父结点的键值均大于子结点。

由最大堆的定义,可以很容易的理解最小堆,即所有父结点的键值均小于子结点。

堆的内存形式有两种,一种是链表,一种是数组。

对于一个堆,常用的操作有两种,插入一个新的结点和删除堆顶。

向堆插入一个结点,首先要保证堆依然是一个完全二叉树,即必须保证一行(也就是一层)构建完成才能继续添加下一层的结点。这就意味着完全二叉树新增加结点的位置是唯一固定的。对应数组来说,就是在数组的末尾增加一个元素。

进一步,对这个完全二叉树进行调整,即移动父结点和子结点的相互位置关系,使其满足条件而重新成为堆。这种调整可以简单的看成是一些列的上浮(shift-up)操作。可以看看下面这个简单的图。

可以看到,所谓的shift-up,就是将新插入的结点不停的和其父结点进行比较,如果子结点的键值大于(最大堆)/小于(最小堆)其父结点,那么就对二者进行交换,因为这里是数组,所以仅需要交换结点之间的键值,直到子结点的键值不大于(最大堆)/不小于(最小堆)其父结点。

和插入新的结点类似,删除堆顶,还是首先要保证堆依然是一个完全二叉树,即必须保证一行(也就是一层)全部删除之后才能继续删除上一层的结点。这就意味着完全二叉树删除的结点的位置是唯一固定的。对应数组来说,就是删除数组末尾的元素。

删除堆顶的操作可以分为3步:

步骤1和2非常简单,执行完成之后,新的完全二叉树如图所示:

步骤3是问题的重点和难点,可以简单的看成是一些列的下沉(shift-down)操作。

对于某个结点(parent),所谓的shift-down,包括以下子步骤(这里以最大堆为例):

以上面的堆为例:

构建堆有两种方式,一种是从无到有,也就是一个不断插入结点的过程;而另一种就是在原有完全二叉树的基础上,按照某种规则对结点进行调整。

从原理上说,从无到有的构建堆比较简单,对于每一个新增结点,对其进行插入操作,结果必然是一个堆。

在原有的完全二叉树上进行调整,稍微复杂一些,可以从最后一个非叶结点开始,对每个非叶结点进行shift-down操作。

该操作的难点在于如何找到“非叶结点”和“最后一个非叶结点”。考虑非叶结点的定义,一个结点如果 有至少一个子结点 ,那么就称其为 非叶结点 。因此,我们只要遍历所有的结点(根结点除外)的父结点,就可以遍历所有的 非叶结点 。知道了如何找到“非叶结点”,找出“最后一个非叶结点”的方法显而易见,最后一个叶结点(数组的末尾)的父结点就是“最后一个非叶结点”。

通过之前的章节,不难看出,堆操作的核心是两个步骤:shift-down和shift-up,更进一步,这两个操作都是递归的。

不仅在面试中,堆在日常工作中也经常被使用。堆经常会被作为优先队列来使用,常见于例如任务调度,数组合并等场景。

在java中,优先队列实现了堆的数据结构【1】。我之前的一篇文章 Java 优先队列 (PriorityQueue) 对优先队列进行了简单介绍,可以参考。
【1】 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

其他参考文章:
【2】 最大堆(创建、删除、插入和堆排序)
【3】 数据结构:堆(Heap)
【4】 关于堆结构的详解
【5】 构建堆的时间复杂度
【6】 最大堆的插入/删除/调整/排序操作(图解+程序)(JAVA)

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
景联文科技
2024-06-11 广告
杭州景联文科技有限公司专注于大模型数据集的研发与应用。我们深知,在人工智能飞速发展的时代,数据是驱动模型优化的核心动力。因此,我们致力于构建丰富、多元的大模型数据集,涵盖各行各业,为AI模型提供充足的“养分”。通过不断积累与优化,我们的数据... 点击进入详情页
本回答由景联文科技提供
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式