苏州企业网站建设设计,网站二级导航,互利互通网站建设,江西专业网站建设1 引言
什么是堆#xff1f;
堆是一种满足以下条件的树#xff1a;#xff08;树这一篇可以参考我的文章数据结构秘籍#xff08;三#xff09;树 #xff08;含二叉树的分类、存储和定义#xff09;-CSDN博客#xff09;
堆中的每一个结点值都大于等于#xff08…1 引言
什么是堆
堆是一种满足以下条件的树树这一篇可以参考我的文章数据结构秘籍三树 含二叉树的分类、存储和定义-CSDN博客
堆中的每一个结点值都大于等于或小于等于子树中所有结点的值。 很多博客说堆是完全二叉树其实并非如此堆不一定是完全二叉树只是为了方便存储和索引我们通常用完全二叉树的形式来表示堆事实上广为人知的斐波那契堆和二项堆就不是完全二叉树,它们甚至都不是二叉树。 • 二叉堆是一个数组它可以被看成是一个 近似的完全二叉树。——《算法导论》第三版 判断一下下面给出的图是否是堆 第1 个和第 2 个是堆。第 1 个是最大堆每个节点都比子树中所有节点大。第 2 个是最小堆每个节点都比子树中所有节点小。第3个不是在第三个中有的结点比子结点小有的比子结点大不符合堆的特性。 2 堆的用途
当我们只关心所有数据中的最大值或者最小值存在多次获取最大值或者最小值多次插入或删除数据时就可以使用堆。
对比有序数组而言初始化一个有序数组时间复杂度是 O(nlog(n))查找最大值或者最小值时间复杂度都是 O(1)但是涉及到更新插入或删除数据时时间复杂度为 O(n)即使是使用复杂度为 O(log(n)) 的二分法找到要插入或者删除的数据在移动数据时也需要 O(n) 的时间复杂度。
相对于有序数组而言堆的主要优势在于插入和删除数据效率较高。 因为堆是基于完全二叉树实现的所以在插入和删除数据时只需要在二叉树中上下移动节点时间复杂度为O(log(n))相比有序数组的 O(n)效率更高。
不过需要注意的是Heap 初始化的时间复杂度为 O(n)而非O(nlogn)。 3 堆的分类
堆分为最大堆和最小堆。二者的区别在于结点的排序方式。
最大堆堆中的每一个结点的值都大于等于子树中所有结点的值。最小堆堆中的每一个结点的值都小于等于子树中所有结点的值。
在下图中图1是最大堆图2是最小堆。 4 堆的存储
之前介绍树的时候说过由于完全二叉树的优秀性质利用数组存储二叉树即节省空间又方便索引若根结点的序号为 1那么对于树中任意节点 i其左子节点序号为 2*i右子节点序号为 2*i1。
为了方便存储和索引二叉堆可以用完全二叉树的形式进行存储。存储的方式如下图所示 5 堆的操作
堆的更新操作主要包括两种插入元素和删除堆顶元素。操作过程需要着重掌握和理解。
5.1 插入元素
在堆内进行插入的时候我们会将插入的元素放到最后
5.1.1 将要插入的元素放到最后 5.1.2 从底向上如果父结点比该元素小则该结点和父结点交换 直到无法交换 5.2 删除堆顶元素这里拿最大堆举例 根据堆的性质可以知道最大堆的堆顶元素为所有元素中最大的最小堆的堆顶元素是所有元素中最小的。当我们需要多次查找最大元素或者最小元素的时候可以利用堆来实现。
删除堆顶元素后为了保持堆的性质需要对堆的结构进行调整我们将这个过程称之为“堆化”堆化的方法分为两种
一种是自底向上的堆化上述的插入元素所使用的就是自顶向上的堆化元素是从最底部向上移动。另一种是自顶向下堆化元素由最顶部向下移动。
5.2.1 自底向上堆化
打个比方如果一个公司里出现了boss离职的情况该怎么办看下文
首先删除堆顶元素使得数组中下标为1的位置空出。 那谁来顶替这个位置必须是数足够大。所以我们比较根结点的左子结点和右子结点也就是下标为2,3的数组元素将较大的元素填充到根结点的位置。 这时候空出来的位置就依次往下递归谁有能力谁就上。也就是说一直循环比较空出位置的左右子结点并将大者移至空位直到遍历到堆的最底部。 我们可以看到这个时候已经完成了自底向上的堆化没有元素可以填补空缺了但是我们可以看到数组中出现了空白这将会导致存储空间的浪费。
5.2.2 自顶向下堆化
自顶向下堆化有一个特殊的点就是我们需要将堆的最后一个元素从末尾的位置提到堆顶根结点上来再进行堆化。 我们不断的将这个原来的 末尾元素不断地与左右子结点的值进行比较和较大的子结点交换位置直到无法交换为止 可能有的小伙伴要问了这两个也没有什么太大的区别啊重点就在自顶向下堆化不会产生气泡。
5.3 总结堆的操作
插入元素先将元素放置到元素末尾再自底向上堆化使末尾元素上浮。删除堆顶元素将末尾元素放置堆顶再自顶向下堆化将堆顶元素下沉。也可以自底向上堆化只是会产生空缺浪费存储空间。最好采用自顶向下的堆化方式。 6 堆排序
堆排序的过程分为两步
第一步是建堆将一个无序的数组建立为一个堆。第二步是排序将堆顶元素取出然后对剩下的元素进行堆化反复迭代直到所有的元素被取出为止。
6.1 建堆
建堆的过程就是一个对所有非叶子结点的自顶向下堆化过程。
什么是非叶子结点就是最后一个结点的父结点及它之前的元素都是非叶子结点具体可以了解另外一篇关于树的相关内容这里不详谈。数据结构秘籍三树 含二叉树的分类、存储和定义-CSDN博客文章浏览阅读689次点赞27次收藏22次。根结点的序号为1对于每个结点Node假设它存储在数组中下标为i的位置那么它的左子结点就存储在2i的位置它的右子结点就存储在下标为2i1的位置。二叉树的第i层最多拥有2的n-1次方个结点深度为k的二叉树至多有2^(k1)-1个结点满二叉树至少有2的n次方个结点这里面的k为深度。二叉树的先序遍历是先输出根结点再遍历左子树最后遍历右子树遍历右子树和左子树的时候同样 遵循先序遍历的规则也就是说我们可以递归实现先序遍历。并且二叉树的分支具有左右次序不能随意颠倒。https://blog.csdn.net/rc1596919047/article/details/145934474?spm1001.2014.3001.5501也就是说如果结点个数为n那么我们需要对n/2到1的结点进行自顶向下堆化。 将初始的无序数组抽象为一棵树图中的结点个数为6个所以456结点为叶子结点1,2,3结点为非叶子结点所以要对1-3号结点进行自顶向下堆化注意顺序是从后往前堆化从3号结点开始一直到1号结点。为什么是结点3n为6非叶子结点就是3-1。
例如这张图非叶子结点就是从5开始到1。画的比较抽象不喜勿喷
回去看3号结点堆化结果 2号结点堆化结果 1号结点堆化结果 至此数组所对应的树已经成为了一个最大堆建堆完成。
额外注意的是堆化是一个完整的过程而非一个步骤。 6.2 排序
由于堆顶元素是所有元素中最大的所以我们重复取出堆顶元素将这个最大的堆顶元素放置数组末尾并对剩下的元素进行堆化即可。
现在思考两个问题
删除堆顶元素后需要执行自顶向下堆化还是自底向上堆化取出的堆顶元素存在哪新建一个数组存吗
先回答第一个问题我们需要执行自顶向下堆化这个堆化一开始要将末尾元素移动至堆顶这个时候末尾的位置就空出来了由于堆中的元素已经减小这个位置不会再被使用所以我们可以将取出的元素放在末尾。这其实就是做了一次交换操作将堆顶和末尾的元素调换位置从而将取出堆顶元素和堆化的第一步将末尾元素放置根结点进行合并。
取出第一个元素并堆化 取出第二个元素并堆化 取出第三个元素并堆化 取出第四个元素并堆化 取出第五个元素并堆化 取出第六个元素并堆化 堆排序就此完成。 如果觉得我的讲解有不足之处可以在评论区发表意见我会及时采纳改正。更细致的可以去看一看这篇文章
数据结构堆(Heap)详解-堆的建立、插入、删除、最大堆、最小堆、堆排序等_最大堆 heap 是一个什么样的存在?-CSDN博客文章浏览阅读7.9w次点赞153次收藏447次。基本概念1、完全二叉树若二叉树的深度为h则除第h层外其他层的结点全部达到最大值且第h层的所有结点都集中在左子树。2、满二叉树满二叉树是一种特殊的的完全二叉树所有层的结点都是最大值。什么是堆堆英语heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质堆中某个节点的值总是不大于或不小于其父节点的值..._最大堆 heap 是一个什么样的存在?https://blog.csdn.net/xiaomucgwlmx/article/details/103522410
