精华内容
下载资源
问答
  • 插入法建堆是将数组1中元素逐个插入...调整法建堆自底向上依次调整,一棵子树中最大节点值与根节点交换,最小那个节点位置在本次调整中不作改变。 而插入法建堆结果与插入顺序和值大小有关。以大顶堆为例,

           建堆的方式大体有两种,一种是插入法,一种是调整法,其中以调整法比较常见。由于他们的建堆的思路不同,所以两种方法建堆结果可能不一样。

           插入法建堆是将数组1中的元素逐个插入到数组2中建立一个堆。以小根堆为例,每插入一个关键字就与其父节点的关键字比较大小,如果父节点的关键字较大则交换,然后依次自底地向上调整使之符合小根堆的特性。在某棵已插入根节点的子树中,当插入左节点时,左节点与根节点交换,插入右节点时,右节点与根节点交换,那么这种情况下这颗子树三个节点的位置都发生改变了。因此插入法建堆结果与插入的顺序和值大小有关。

           调整法建堆是自底向上依次调整,一棵子树中最小的节点值与根节点交换,最大的那个节点位置在本次调整中不作改变。即这种方法建堆有一个节点位置不变。

            下面是插入法和调整法建堆的Python代码:

    import random
    import datetime
    
    #make random file
    def creatIntRandom():
        count = 100
        output = open('data_100.txt','w+')
        while count:
            output.write(str(random.randint(0,1000001)) + '\n')
            count = count - 1
        output.close
    
    def txtToList():
        int_list = []
        in_file = open('data.txt')
        in_text = in_file.readlines()   
        for line in in_text:
            num = int(line[0 : len(line) - 1])
            int_list.append(num) 
        in_file.close()
        return int_list
    
    #----------------------------------
    def minHeapify(list, heapsize, index):
        left = 2*index + 1
        right = 2*index + 2
        mini = index
        if left < heapsize:
            if list[mini] > list[left]:
                mini = left
            if right < heapsize and list[mini] > list[right]:
                mini = right
        if mini != index:
            list[mini], list[index] = list[index], list[mini]
            minHeapify(list, heapsize, mini)
    
    def buildMinHeap_1(list):
        heapSize = len(list)
        if heapSize < 2:
            return
        for i in range(heapSize/2 - 1, -1, -1):
            minHeapify(list, heapSize, i)
    
    def heapSort_1(list):
        buildMinHeap_1(list)
        for i in range(len(list) - 1, -1, -1):
            list[0], list[i] = list[i], list[0]
            minHeapify(list, i, 0)
        return list    
    
    #-------------------------------------------
    def buildMinHeap_2(list_1):
        heapsize = 0
        list_2 = [0]*(len(list_1) + 1)
        for i in range(len(list_1)):
            heapsize = i + 1
            list_2[heapsize] = list_1[i]
            while heapsize > 2 and list_2[heapsize/2] > list_2[heapsize]:
                list_2[heapsize], list_2[heapsize/2] = list_2[heapsize/2], list_2[heapsize]
                heapsize/=2
        return list_2[1:len(list_2)]
    
    def heapSort_2(list):
        list_2 = buildMinHeap_2(list)
        for i in range(len(list)-1, -1, -1):
            list_2[0], list_2[i] = list_2[i], list_2[0]
            minHeapify(list_2, i, 0)
        return list_2
    
    #------------------------------------------
    def verify(list):
        for i in range(len(list) - 1):
            if list[i] >= list[i+1]:
                pass
            else:
                return False
        return True
    
    def test():
        list_in = txtToList()
    
        time_start_1 = datetime.datetime.now()
        list_out_1 = heapSort_1(list_in)
        time_end_1 = datetime.datetime.now()
        #print list_out_1
        print verify(list_out_1)
        print (time_end_1 - time_start_1)
    
        time_start_2 = datetime.datetime.now()
        list_out_2 = heapSort_2(list_in)
        time_end_2 = datetime.datetime.now()
        #print list_out_2
        print verify(list_out_1)
        print (time_end_2 - time_start_2)
    
    #creatIntRandom()
    test()
    


            下图是对100W个随机产生的整数进行堆排序的运行结果:

        

     


            调整法的时间复杂度:建堆耗时0.5NlogN,排序耗时NlogN,累计1.5NlogN。
            插入法的时间复杂度:建堆耗时NlogN,排序耗时NlogN,累计2NlogN。
            从以上的比较中可以看出,虽然两种方法的时间复杂度在数量级是一样的,但是由于建堆所耗费的时间不同,总体时间有所不同,从上图执行的结果可以看出来:上面是调整法建堆并排序所耗时间,下面是插入法建堆并排序所耗时间。基本符合上述分析。




    展开全文
  • 插入法建堆

    千次阅读 2012-09-26 11:31:41
    插入法建堆是将数组A中元素...调整法建堆自底向上依次调整,一棵子树中最大节点值与根节点交换,最小那个节点位置在本次调整中不作改变。 而插入法建堆结果与插入顺序和值大小有关。以大顶堆为例,在某棵已

    插入法建堆是将数组A中的元素逐个插入到数组B中建立一个堆。每插入一个关键字就与其父节点的关键字比较大小,如果父节点的关键字较小则交换,然后依次自低地向上调整使之符合大(小)顶堆的特性。

    插入法建堆与调整法建堆可能结果不一样。调整法建堆是自底向上依次调整,一棵子树中最大的节点值与根节点交换,最小的那个节点位置在本次调整中不作改变。

    而插入法建堆结果与插入的顺序和值大小有关。以大顶堆为例,在某棵已插入根节点的子树中,当插入左节点时,左节点与根节点交换,插入右节点时,右节点与根节点交换,那么这种情况下这颗子树三个节点的位置都发生改变了。而调整法建堆有一个节点位置不变,所以两种方法建堆结果可能不一样。

    下面是插入法建堆的部分代码。

    void Build_Max_Heap(int array1[], int arraysize, int array2[], int &heapsize)
    {
        //将array1中的元素逐个插入到array2中建堆 ,堆初始大小为0 
    	int i=0;
    	for(i=0;i<arraysize;i++)
    	{
    		Max_Heap_Insert(array2, array1[i], heapsize);
    	}
    }
    
    void Max_Heap_Insert(int array2[], int key, int &heapsize)
    {
    	heapsize++;
    	array2[heapsize]=key-1;
    	Heap_Increase_Key(array2,heapsize,key);	
    }
    
    void Heap_Increase_Key(int array[], int i, int key)//往堆中插入关键字建堆 
    {
    	if (key<=array[i])
    	{
    		cout<<"New key iS smaller than current key!"<<endl;
    		return;
    	}
    	array[i]=key;
    	while (i>1&&array[i/2]<array[i])
    	{
    		Exchange(array[i],array[i/2]);
    		i=i/2;
    	}
    }


     

    展开全文
  • 由于建堆过程自底向上,以交换作为主要操作,因此第 \(i\) 层任意节点在最不利情况下, 需要经过 \((n - i)\) 次交换操作才能完成以该节点为堆根节点的建堆过程。 因此,时间复杂度计算如下: \(T(n) = 2^0 * (n - 0...

    建堆的复杂度先考虑满二叉树,和计算完全二叉树的建堆复杂度一样。

    对满二叉树而言,第 \(i\) 层(根为第 \(0\) 层)有 \(2^i\) 个节点。

    由于建堆过程自底向上,以交换作为主要操作,因此第 \(i\) 层任意节点在最不利情况下,

    需要经过 \((n - i)\) 次交换操作才能完成以该节点为堆根节点的建堆过程。

    因此,时间复杂度计算如下:

    \(T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n) = \sum_{i = 0}^{n}(2^i * (n - i))\)

    将上式乘以 \(2\)得:

    \(2*T(n) = 2^1 * (n - 0) + 2^2 * (n - 1) + ... + 2^{n+1} * (n - n) = \sum_{i = 1}^{n+1}(2^i * (n - i))\)

    原式减去上式得:

    \(2T(n) - T(n) = -n + 2^1 + 2^2 + ... + 2^n = 2 * \frac{1 - 2^n} {1 - 2} - n = 2^{n+1} - 2 - n\).

    上面推导中,\(n\) 为层数编号(自 \(0\) 层根节点开始)。

    故总节点数为 \((1 + 2 + 4 + ... + 2^n) = 2^{n+1} - 1\)

    渐进时,忽略减 \(1\)\(N = 2^{n+1}\)

    所以,\(T(N) = 2^{n+1} - n - 2 = N * (1 - \frac{logN} { N} - \frac{2} {N}) ≈ N\).

    所以,建堆的时间复杂度为 \(O(N)\) ,得证。\(N\)为总节点数。

    转载于:https://www.cnblogs.com/LzyRapx/p/9565305.html

    展开全文
  • 算法导论 — 6.3 建堆

    2018-12-03 22:41:16
    建堆的过程实际上是自底向上地对所有非叶结点调用MAX-HEAPIFY过程。由于叶结点没有孩子,所以每一个叶结点都可以看是只包含一个元素最大堆。而自底向上地调用MAX-HEAPIFY,是要保证在处理任意一个结点时候,它...

    笔记

    建堆的过程实际上是自底向上地对所有非叶结点调用MAX-HEAPIFY的过程。由于叶结点没有孩子,所以每一个叶结点都可以看是只包含一个元素的最大堆。而自底向上地调用MAX-HEAPIFY,是要保证在处理任意一个结点的时候,它的子树已经满足了最大堆性质,这是调用MAX-HEAPIFY的必要条件。
      在这里插入图片描述
      BUILD-MAX-HEAP的运行时间为O(n)O(n)。这一结果的推导过程可以参考书本上的描述,这里不做说明。
      下图给出了一个构建最大堆的例子。
      在这里插入图片描述

    练习

    6.3-1 参照图6-3的方法,说明BUILD-MAX-HEAP在数组A = <5, 3, 17, 10, 84, 19, 6, 22, 9>上的操作过程。
      
      在这里插入图片描述

    6.3-2 对于BUILD-MAX-HEAP中第2行的循环控制变量ii来说,为什么我们要求它是从A.length/2⌊A.length/2⌋到1递减,而不是从1到A.length/2⌊A.length/2⌋递增呢?
      
      因为调用MAX_HEAPIFY(A, i)的先决条件是,结点ii的子树必须都已经满足最大堆条件。而节点ii的子树中的结点的下标都比ii要大,因此BUILD-MAX-HEAP中的循环控制变量ii必须是递减的。

    6.3-3 证明:对于任一包含nn个元素的堆中,至多有n/2h+1⌈n/2^{h+1}⌉个高度为h的结点?
      
      首先考虑叶结点,它们的高度h=0h = 0,根据练习6.1-7的结论,含有nn个元素的堆的叶子结点的个数为nn/2=n/2=n/20+1n-⌊n/2⌋=⌈n/2⌉=⌈n/2^{0+1}⌉。因此命题对h=0h = 0是成立的。
      下面把原始堆H0H_0中的叶结点去掉,剩下的元素仍然构成一个堆H1H_1,并且H1H_1中的叶结点就是H0H_0中高度为11的结点。堆H1H_1的大小为n/2⌊n/2⌋,故H1H_1中的叶结点个数为n/2/2n/22⌈⌊n/2⌋/2⌉≤⌈n/2^2 ⌉。即原始堆H0H_0中高度为11的结点至多有n/22=n/21+1⌈n/2^2 ⌉=⌈n/2^{1+1}⌉个。因此,命题对h=1h = 1也是成立的。
      下面把堆H1H_1中的叶结点去掉,剩下的元素也构成一个堆H2H_2,并且H2H_2中的叶结点就是H0H_0中高度为22的结点。堆H2H_2的大小为n/2/2⌊⌊n/2⌋/2⌋(因为堆H1H_1的大小为n/2⌊n/2⌋,根据练习6.1-7的结论,堆H1H_1中的非叶结点个数为n/2/2⌊⌊n/2⌋/2⌋)。堆H2H_2中的叶子结点个数为n/2/2/2n/23⌈⌊⌊n/2⌋/2⌋/2⌉≤⌈n/2^3⌉。即原始堆H0H_0中高度为22的结点至多有n/23=n/22+1⌈n/2^3 ⌉=⌈n/2^{2+1}⌉个。因此,命题对h=2h = 2也是成立的。
      … …
      以此类推,在一个大小为nn的堆中,高度为hh的结点至多有n/2h+1⌈n/2^{h+1}⌉个。

    展开全文
  • 建堆O(n)时间复杂度证明

    千次阅读 2015-07-10 16:31:55
    建堆复杂度先考虑满二叉树,计算完全二叉树建堆复杂度基本相同。...由于建堆过程自底向上,以交换作为主要操作,因此第i层任意节点在最不利情况下,需要经过(n-i)次交换操作才能完成以该节点为堆根节点的建堆过程。
  • STL经典算法集锦<二>之算法

    千次阅读 2012-03-24 19:55:27
    下面将以两种方法建堆:自底向上的建堆(STL和算法导论中使用到的)、自顶向下建堆(即插入建堆的方法) 公共操作: int parent(int i) { return (int)((i-1)/2); } int left(int i) { return 2 * i+1; } ...
  • 我们可以用自底向上的方法利用过程max-heapify把一个大小为n=A.length的数组A[0..n-1]转换为最大。子数组A(下取整n/2.....n-1)中的元素都是叶结点。每个叶结点都可以看成只包含一个元素的。过程build_max_heap(A...
  • (1)自底向上,自右向左遍历建堆。这里底不是指最后一个节点,而是最后一个非叶子节点。每个非叶子节点与其左儿子与右儿子(假如有话)相比,如果父节点小,那么将左右儿子中较大那个与父节点交换,然后递归...
  • 排序

    2018-03-14 18:27:57
    1.完全二叉树的性质从顶至下将完全二叉树从0按层开始标号标号为i的父节点标号为(i-1)/2,左...可以自底向上和自顶向上的两种方式进行建堆。自顶向下是节点从上至下下沉,自底向上是节点从下至上上浮。3.优先级队列优...
  • 如果有一个关键字集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉树顺序存储...创建复制数组找到最初调整位置,即最后一个分支结点自底向上逐步扩大形成向前换一个分支结点插入将待插入元素插入已...
  • 排序:学习记录

    2020-06-14 21:53:38
    通过下沉方式,自底向上进行建堆 ,可以保证当检测到有父节点堆有序时,其所有子堆都是满足堆成立条件。即父节点大于任意两个子节点 下沉排序过程,实质上是在删除最大元素后,堆自我调整过程。调整过程...
  • 建堆 排序算法中堆排序(二) ...方法:自底向上 过程:MAX-HEAPIFY 算法描述: build-max-heap(i){ A.heap-size = A.length for i = [A.length/2] downto 1 Max-heapify(A,i) } 算法正确性证明...
  • 文章目录(二叉)堆简介堆分类堆基本操作计算堆中每个结点父节点、左孩子和右孩子下标维护堆性质:Max_HeapifyMax\_HeapifyMax_Heapify堆插入操作提取并删除堆顶元素修改堆中元素自底向上建堆,任何...
  • 定义二叉是一个数组,可以被看做一个近似的完全二叉树。...可以使用自底向上的方法利用过程maxHeapify(向下调整)把数组A[1-n]转换为。 伪代码 向下调整maxHeapify 伪代码 算法描述 3.向上调整
  • 排序算法——排序

    2020-09-15 16:00:23
    for i in range((heapSize -2)//2,-1,-1): # 自底向上建堆 max_heapify(heap, heapSize, i) def max_heapify(heap,heapSize,root): # 调整列表中元素并保证以root为根堆是一个大根堆 '''
  • 文章目录基本性质存储方式具体实现向上调整swim向下调整sink实现delMax (删除队顶元素)实现insert完整代码建堆自顶向下建堆自底向上建堆堆排序例题寻找第K大元素 基本性质 优先级队列,也叫二叉堆、堆(不要和内存...
  • 排序总结

    2020-09-27 19:45:28
    =n/2所有结点依次”下坠“调整(自底向上处理分支结点),调整规则:小元素逐层”下坠“(与关键字更大孩子交换)。 排序:将栈顶元素加入有序子序列(栈顶元素与栈底元素交换),栈底元素换到栈顶后,需要进行...
  • 第六章 排序

    2020-04-28 15:56:22
    维护堆(自顶向下) FIX-HEAP假设该结点左右子树都是堆, 只需要调整该结点与子女位置关系, 但这样...建堆(自底向上) 从倒数第二层开始, 对每个结点调用FIX-HEAP, 从而保证执行到每个结点时, 它子树已经维护成...
  • 小根 总结

    万次阅读 2012-04-11 15:55:23
    小根 如果有一个关键字集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉树顺序存储 ...3.1自底向上逐步扩大形成 3.2 向前换一个分支结点 小根堆的插入: 1. 将待插入元素插入已
  • 哈夫曼树构造、编码和解码

    千次阅读 2019-06-01 20:33:50
    被问了一天哈夫曼树=_= 于是迫不得已敲了一个… 首先是读字符,统计文章中n种字符每种出现...虽然树是自底向上建的,但实际使用时候只用从根往下跑,所以不必记录父节点。 数完跑dfs就能得到所有叶子结点huffm...
  • 通过分析国内企业很多RPA实战案例发现,他们RPA旅程大多数是以“自底向上方式推进。这主要是源于企业对RPA领域认知不足,领导也没有介入这项工作。在早期缺乏有经验专家指导情况下,企业就冒然启动...
  • 这题很满足可并自底向上许多小根,每个节点先把所有子节点小根给并起来,那么每次决策就是一直取顶直到不能再取,记下num就好了。 但是这么做时间复杂度太大了。 题解 贪心+可并不...
  • 算法初级班--2.mp4

    2018-05-01 22:24:12
    这一章中重点掌握:(1)建最大堆或最小堆有两种方式,第一种为先将所有元素存入数组,然后自底向上调整,再根据需要自顶向下调整。时间复杂度为O(n)第二种为插入建堆(先建立一个空堆,然后每次插入一个元素),...
  • bzoj2809

    2016-09-11 20:56:40
    以前不太知道可并还能自底向上建感觉思路还是非常好 #include #include using std::swap; const int MAXn=100000+9; int head[MAXn],next[MAXn],end[MAXn],ne; inline void add(int a,int b) {  ...
  • 自底向上 D. 信息隐蔽 (38) 索引属于(B) A. 模式 B. 内模式 C. 外模式 D. 概念模式 (39) 在关系数据库中,用来表示实体之间联系是(D) A. 树结构 B. 网结构 C. 线性表 D. 二维表 (40) 将E-R图转换到关系模式时,...

空空如也

空空如也

1 2
收藏数 31
精华内容 12
关键字:

自底向上的建堆