北京网站建设公司司,开题报告风景区网站开发,引用网站代码,佛山公司网站设计团队一.堆
1.堆的定义
堆是计算机科学中一类特殊的数据结构的通常#xff0c;堆通常可以被看做是一颗完全二叉树的数组对象。
堆的特性
1.它是完全二叉树#xff0c;除了树的最后一层结点不需要是满的#xff0c;其他的每一层从左到右都是满的#xff0c;如果最后一层结点不…一.堆
1.堆的定义
堆是计算机科学中一类特殊的数据结构的通常堆通常可以被看做是一颗完全二叉树的数组对象。
堆的特性
1.它是完全二叉树除了树的最后一层结点不需要是满的其他的每一层从左到右都是满的如果最后一层结点不是满的那么要求左满右不满。 2.它通常用数组来实现
具体方法就是讲二叉树的结点按照层级顺序放入数组中根结点在位置1它的子节点在位置2和3而子节点的子节点则分别在位置4,5,6,7以此类推。 如果一个结点的位置为k则它的父结点的位置为【k/2】,而它的两个子结点的位置则分别为2k和2k1。这样在不适用指针的情况下我们也可以通过计算数组的索引在书中上下移动从a[k]向上一层就令k等于k/2向下一层就令k等于2k或2k1。
3.每个结点都大于等于它的两个子结点这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点但这两个子结点的书序并没有做规定更我们之前学习的二叉查找树是有区别的。
2.堆的API设计 3.堆的实现
【1】insert插入方法的实现
堆事用数组完成数据元素的存储的由于数组的底层是一串连续的内存地址所以我们要往堆中插入数据我们只能往数组中从索引0处开始依次往后存入数据但是堆中对元素的顺序是有要求的每一个结点的数据要大于等于它的两个子结点的数据所以每次插入一个元素都会使得堆中的数据顺序变乱这个时候我们就需要通过一些方法让刚才插入的这个数据放入最合适的位置。 所以如果往堆中新插入元素我们只需要不断的比较新结点a[k]和它的父节点a[k/2]的大小然后根据结果完成数据元素的交换就可以完成堆的有序调整。
【2】delMax删除最大元素方法的实现
由堆的特性我们可以知道索引1处的元素也就是根结点就是最大的元素当我们吧根结点的元素删除后需要有一个新的结点的出现这时我们可以暂时吧堆中最后一个元素放到索引1处充当根结点但是它有可能不满足堆的有序性需求这个时候我们需要通过一些方法让这个新的根结点放入到合适的位置。 所以当删除掉最后一个元素后只需要将最后一个元素放到索引1处并不断的拿着当前结点a[k]与它的子结点a[2k]和a[2k1]中的较大者交换位置即可完成堆的有序调整。
4.堆排序
【1】实现步骤 1.构造堆 2.得到堆顶元素这个值就是最大值 3.交换堆顶元素和数组中的最后一个元素此时所有元素中的最大元素已经放到合适的位置 4.对堆进行调整重新让除了最后一个元素的剩余元素中额最大值放到堆顶 5.重复2-4这个步骤知道堆中剩一个元素为止。
【2】堆构造过程
堆的构造最直观的想法就是另外再创建一个和新数组然后从左网友遍历元素组没得到一个元素后添加到新数组中并通过上浮对堆进行调整最后新的数组就是一个堆。 上述的方式虽然很直观也很简单但是我们可以用更聪明的一点的办法完成它。创建一个新数组把原数组0~length-1的数据拷贝到新数组的1~length处再从新数组长度的一半处开始往1索引处扫描从右往左然后对扫描到的每一个元素左下沉调整即可。
【3】堆排序过程
对构造好的堆我们只需要做类似于堆的删除操作就可以完成排序。 1.将堆元素和堆中最后一个元素交换位置 2.通过对堆顶元素下沉调整堆把最大的元素放到堆顶此时最后一个元素不参与堆的调整因为最大的数据已经到了数组的最右边 3.重复1-2步骤直到堆中剩最后一个元素。
11堆排序算法_哔哩哔哩_bilibili
