精华内容
下载资源
问答
  • 堆排序算法之初始堆建立总结

    万次阅读 多人点赞 2016-12-01 23:52:52
    堆排序算法之初始堆建立总结@(算法学习)关于堆的插入和删除有过一篇思考,但是关于初始堆构建,没有总结。简单说就下面几个要点(以大顶堆为例): 首先根据序列构建一个完全二叉树 在完全二叉树的基础上,从最后...

    堆排序算法之初始堆建立总结

    @(算法学习)

    关于堆的插入和删除有过一篇思考,但是关于初始堆的构建,没有总结。

    简单说就下面几个要点(以大顶堆为例):

    • 首先根据序列构建一个完全二叉树
    • 在完全二叉树的基础上,从最后一个非叶结点开始调整:比较三个元素的大小–自己,它的左孩子,右孩子。分为三种情况:
      • 自己最大,不用调整
      • 左孩子最大,交换该非叶结点与其左孩子的值,并考察以左孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理
      • 右孩子最大,交换该非叶结点与其右孩子的值,并考察以右孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理

    就这些基本要求,就可以解决这一类的手工计算问题。举个例子:

    比如:一组记录(5,11,7,2,3,17)利用大顶堆排序方法建立初始堆为?

    分析:首先建立完全二叉树。

    这里写图片描述

    再从最后一个非叶结点开始调整。

    第一次交换7,17的位置。

    这里写图片描述

    展开全文
  • 堆排序之建初始堆

    千次阅读 2019-08-28 15:25:32
    答案是c,但是之前只接触插入法建堆,没了解筛选法建初始堆,于是网上冲浪,查找了一波解析,于是有了现在这个思路总结(看半天也没有看到比较靠谱的代码),然后总结了一下,按照这种思路,能得到C答案,但仍然存在...

    在牛客网上看到一道题

    答案是c,但是之前只接触插入法建堆,没了解筛选法建初始堆,于是网上冲浪,查找了一波解析,于是有了现在这个思路总结(看半天也没有看到比较靠谱的代码),然后总结了一下,按照这种思路,能得到C答案,但仍然存在一点疑惑(初始堆难道不应该是大顶堆或者小顶堆嘛,这结果也不是呀,还是说,有什么定义我不知道?求解),需要再去看看书。。。

    最终还是觉得答案是错的,按照概念重新更正了图解和伪代码。感觉答案应该是:-1,4,7,8,20,15,7,9

    堆排序建初始堆有两种思路:

    筛选法:将当前待排序的n个记录为作为一个大小为n的一维数组,然后向下取整parent=n/2开始比较(即为最后一个非叶节点),用图和一段伪代码做了介绍(待指正)

    筛选法构造初始堆
    筛选法构造初始堆图解

    伪代码 

    
    for(int i=n/2;i>0;i--){
        par = i;//父节点
        while(par*2<=n){
            lch = par*2;//左子节点
            rch = lch+1;//右子节点
            min = lch;
            if(rch<=n){//有两个子节点
                if(arr[lch]>arr[rch]){
                    min = rch;
                }
            }
            if(arr[min]<arr[par]){
                swap(arr,min,par);
                par = min;    //往下遍历
            }
        }
        
    }

    插入法:将n个记录依次插入二叉树中,若其比父节点值小,则浮操作,直到其比父节点大

    展开全文
  • 堆排序建立初始堆

    万次阅读 2020-01-08 19:35:34
    例1.有一组记录的排序码为 (3,5,4,7,1,2),则利用堆排序的方法建立的初始堆为 _____________?

    例1.有一组记录的排序码为 ( 3 , 5 , 4 , 7 , 1 , 2 ) (3, 5, 4, 7, 1, 2) (3,5,4,7,1,2),则利用堆排序的方法建立的初始堆为 _____________?

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    所以初始堆为 ( 7 , 5 , 4 , 3 , 1 , 2 ) (7,5,4,3,1,2) (7,5,4,3,1,2)

    展开全文
  • 堆排序初始堆的时间复杂度

    千次阅读 2018-07-19 23:22:12
    堆排序建立初始堆时, 本质上是一个一维数组中, 元素间的两两比较, 其时间复杂度随着数组的规模线性增加 .  时间复杂度为O(n). 不知道推导不知所谓的公式意义何在!...

    堆排序建立初始堆时,  本质上是一个一维数组中, 元素间的两两比较, 其时间复杂度随着数组的规模线性增加 .

     时间复杂度为O(n). 不知道推导不知所谓的公式意义何在!

    展开全文
  • 堆排序算法之初始堆建立

    万次阅读 2019-07-01 20:47:54
    以大顶堆为例(初始操作复杂度是 O(n)) 1.首先根据序列构建一个完全二叉树 2.在完全二叉树的基础上,从最后一个非叶结点开始调整:比较三个元素的大小–自己,它的左孩子,右孩子。分为三种情况: 自己最大,不用...
  • 堆排序创建初始堆

    万次阅读 2015-04-01 07:49:17
    红色部分实际上是创建初始堆的核心代码 )。 代码实现: #include void print_array(int b[],int n) {  int i;  for(i=0;i;i++)  printf("%d ", b[i]); } void CreateHeap(int b[], int i, ...
  • 堆排序-如何构造初始堆

    千次阅读 2016-09-20 17:40:00
      没办法从word中直接粘贴进来,截的图。   1、排序中的
  • 构建大根

    2019-09-15 10:00:36
    序列——排序-大根(大顶) 1.小根 如果根是儿童的存在留下的根值左孩子小于值;如果根是儿童的权利的存在的根值比他们的孩子的权利少值。 2.大根 如果根是儿童的存在留下的根值多名离开自己的孩子值。子女...
  • 一、已知前序遍历、中序遍历求后序遍历(可参考:link) 首先,对于 根据前序遍历可知,G为根节点,在中序遍历中找到G,根据中序遍历的特点可知,G前面的部分为左子树 二、哈弗曼编码 三、建立初始堆
  • 构建堆

    千次阅读 2017-12-10 19:34:53
    排序中,最初的步骤就是建立一个。之前在一些公司的笔试题上面见到一些与建过程相关的题目,因为当时对建过程有个误解,所以经常选错。之前一直以为是在完全二叉树中依次插入序列中的元素,每插入一个元素,...
  • python的heapq模块可以快速构建堆。只是heapq只能构建小根,不能构建大根。 import heapq data2 = [1,5,3,2,9,5] heapq.heapify(data2) print(data2) #输出:[1, 2, 3, 5, 9, 5] 大根的做法: import ...
  • 初始化小根图示

    2020-11-15 19:27:11
    排序 排序分为 1、插入排序:直接插入、折半插入、希尔 2、选择排序:简单选择、排序 3、交换排序:冒泡、快速 4、归并排序、基数排序 先记录下如何初始化小根
  • 数据结构 - 初始化最大、最小

    千次阅读 2019-05-04 10:50:28
    2. 初始的步骤 首先根据序列构建一个完全二叉树 (最大为例)在完全二叉树的基础上,从最后一个非叶结点开始调整(可理解为从右下角):比较三个元素的大小–自己,它的左孩子,右孩子。分为三种情况: 自己...
  • 采用自底向上方式构建二叉的理论分析、Python实现以及O(n)最坏时间复杂度分析
  • 排序(C++源码)

    2009-05-06 19:33:43
    用C++实现的 堆排序,包括恢复堆,构建初始堆
  • 排序及GOLANG代码实现

    千次阅读 2018-11-01 15:07:09
    一、什么是堆排序 堆排序是利用堆这种数据结构而设计的一种...其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中,需交换n-1次,而重建堆的过程中,根据完全二叉树的性质,[log2(n-1),log2(n-2)…1]逐步递...
  • (2)将根节点最大的叫做最大或大根,根节点最小的叫做最小或小根。 (3)是非线性数据结构,相当于一维数组,有两个直接后继。 的定义: (1)n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系...
  • 最小 构建、插入、删除的过程图解

    万次阅读 多人点赞 2016-05-21 00:47:02
    最小构建、插入、删除的过程。搞懂最小的相应知识后,最大与此类似。 2.最小示例 3.最小构建  初始数组为:9,3,7,6,5,1,10,2  按照完全二叉树,将数字依次填入。  填入后,找到最后一个...
  • 1. 构建初始堆 (大顶堆 或 小顶堆); 2. 逐渐从堆中取出顶部元素,重新构造堆,然后再取出顶部元素,循环直到堆为空。 正式开始,首先我们来如何构建初始堆。因为堆是一个二叉树,为了更清楚的描述,在这篇文中我...
  • 构建堆的时间复杂度

    万次阅读 多人点赞 2017-02-26 19:11:41
    大顶堆、小顶堆是一种很常用的数据结构,例如常见的排序和topk算法,在很多应用场景中,我们经常会关注算法时间复杂度和空间复杂度,众所周知构建堆的时间复杂度是o(n),那么为什么是o(n)?本文主要跟大家讨论下这...
  • 初始序列为1 8 6 2 5 4 7 3一组数采用排序,当建(小根)完毕时,所对应的二叉树中序遍历序列为:() 8 3 2 5 1 6 4 7 3 2 8 5 1 4 6 7 3 8 2 5 1 6 7 4 8 2 3 5 1 4 7 6 A ...
  • 1.简介  最小是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子...最小构建、插入、删除的过程。搞懂最小的相应知识后,最大与此类似。 2.最小示例 3.最小构建  初始数组为
  • 利用数组实现的排序

    千次阅读 2017-03-22 13:38:10
    void HeapSort(int a[],int n) ... i--){//构建初始堆 HeapAdjust(a,i,n); } for(i = n; i > 1; i--){//不断输出最大元素进行排序,输出后继续调整 swap(a,1,i); HeapAdjust(a,1,i-1); } } void HeapA
  • 排序(c语言)

    千次阅读 2018-03-29 20:31:05
    堆排序的基本思想及步骤 堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列...构建初始堆(升序建大堆,降序建小堆) a.给定一个无序数组: b.创建一个大堆 将根节点与最后一个叶子节点进...
  • 如何构建一个大根

    千次阅读 多人点赞 2020-06-18 18:18:23
    数组可以看成是一个完全二叉树,大根是一个完全二叉树 构造大根 例子1:[O(N)---->从下到上] 因为是对父节点-左/右孩子节点之间的约束,所以从最后一个非叶子节点开始调整。 注意每次交换后,都要对下一...
  • 最详细的最小堆构建、插入、删除的过程图解

    万次阅读 多人点赞 2016-09-30 17:22:09
    1.简介 ... 最小是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值...最小构建、插入、删除的过程。搞懂最小的相应知识后,最大与此类似。 2.最小示例 3.最小构建  
  • 数据结构 小顶堆建过程 构建过程

    千次阅读 2021-02-26 18:35:22
    本文以图解的方式,说明最小构建、插入、删除的过程。搞懂最小的相应知识后,最大与此类似。 最小示例: 【二】最小的操作 最小构建初始数组为:9,3,7,6,5,1,10,2 按照完全二叉树,将数字...
  • 本文以最小为例,构建堆的过程是首先初始化一个数组a,其中a[0]存数组的长度n,即第一个有效元素从a[1]开始,这样保证左孩子为2*i,右孩子为2*I+1;然后从(n - 1)/2开始,每次向下调整一个元素,直到n = 0。 ...
  • 排序(Heap Sort)

    千次阅读 2019-09-27 16:50:07
    排序(Heapsort)是指利用...将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此初始的无序区; 将顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,697
精华内容 33,478
关键字:

如何构建初始堆