`

第六章堆排序之“对d叉堆的分析”(思考题6-2)

阅读更多

d叉堆在数组中如何表示:

(1)若某个子节点索引为i,则它的父节点的索引为(i-2)/d+1,向下取整。

(2)若某个父节点索引为i,则它的第j个子节点的索引为d*(i-1)+j+1。

下面的程序是用插入法建立d叉最大堆,并显示了一次去掉和返回堆顶元素后剩余堆的情况。

其中 “调整d叉堆” 的时间复杂度都为O(dlogd(n)),d为底哦。(纵向进行logd(n)(即深度)次,每次再横向比较d次即和自己的d个节点分别进行比较。)

“插入元素到d叉堆”的时间复杂度为O(logd(n)),d为底哦。(只是和父节点相比,即只进行纵向运动)

 

  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #include <time.h>  
  4.   
  5. #define BUFFER_SIZE 10  
  6. //堆调整  
  7. void MaxHeapIfy(int *a,int i,int heapSize,int d)  
  8. {  
  9.     int largest=0;  
  10.     int tmp=0;  
  11.     int j=0;  
  12.     int child=0;  
  13.     int b[d+1];  
  14.     for(j=1;j<=d;j++)  
  15.     {  
  16.         b[j]=d*(i-1)+j+1;//计算d叉堆节点i的每个子女j的索引   
  17.     }  
  18.     largest=i;  
  19.     for(j=1;j<=d;j++)  
  20.     {  
  21.         child=b[j];  
  22.         if(child<=heapSize&&a[largest]<a[child])  
  23.         {  
  24.             largest=child;  
  25.         }  
  26.     }  
  27.     if(largest!=i)  
  28.     {  
  29.         tmp=a[i];  
  30.         a[i]=a[largest];  
  31.         a[largest]=tmp;  
  32.       
  33.         MaxHeapIfy(a,largest,heapSize,d);  
  34.     }  
  35. }   
  36.   
  37. //去掉并返回堆顶元素  
  38. int HeapExtractMax(int *a,int *heapSize,int d)  
  39. {  
  40.     int tmp=a[1];  
  41.     a[1]=a[*heapSize];  
  42.     (*heapSize)--;  
  43.     MaxHeapIfy(a,1,*heapSize,d);  
  44. }   
  45.   
  46. //将最大堆指定元素x的关键字增大到k,k要大于x原关键字   
  47. void HeapIncreaseKey(int *a,int x,int k,int d)  
  48. {  
  49.     int tmp=0;  
  50.     if(k<=a[x])  
  51.     {  
  52.         return;  
  53.     }  
  54.     a[x]=k;  
  55.     while(x>1&&a[x]>a[(x-2)/d+1])  
  56.     {  
  57.         tmp=a[x];  
  58.         a[x]=a[(x-2)/d+1];  
  59.         a[(x-2)/d+1]=tmp;  
  60.         x=(x-2)/d+1;  
  61.     }  
  62. }  
  63. //插入元素到最大堆   
  64. void MaxHeapInsert(int *a,int k,int *heapSize,int d)  
  65. {  
  66.     int tmp=k-1;  
  67.     (*heapSize)++;  
  68.     a[*heapSize]=tmp;  
  69.     HeapIncreaseKey(a,*heapSize,k,d);  
  70. }  
  71.   
  72. //插入法建堆  
  73. void BuildMaxHeap(int *b,int len,int *a,int *heapSize,int d)  
  74. {  
  75.     int i=0;  
  76.     for(i=0;i<len;i++)  
  77.     {  
  78.         MaxHeapInsert(a,b[i],heapSize,d);  
  79.     }  
  80. }   
  81. int main()  
  82. {  
  83.     int i=0;  
  84.     int j=0;  
  85.     int heapSize=0;  
  86.     int d=3;  
  87.     int a[BUFFER_SIZE+1];  
  88.     int b[BUFFER_SIZE];  
  89.     //随机生成k个链表,k=4   
  90.     srand((unsigned)time(NULL));  
  91.     for(i=0;i<BUFFER_SIZE;i++)  
  92.     {  
  93.         b[i]=rand()%BUFFER_SIZE;  
  94.     }   
  95.     printf("随机生成的链表:\n");  
  96.     for(i=0;i<BUFFER_SIZE;i++)  
  97.     {  
  98.         printf("%d ",b[i]);  
  99.     }  
  100.       
  101.     printf("\n插入法建堆:\n");   
  102.     BuildMaxHeap(b,BUFFER_SIZE,a,&heapSize,d);  
  103.     for(i=1;i<=heapSize;i++)  
  104.     {  
  105.         printf("%d ",a[i]);  
  106.     }  
  107.       
  108.     printf("\n去掉并返回堆顶元素:\n");  
  109.     HeapExtractMax(a,&heapSize,d);  
  110.     for(i=1;i<=heapSize;i++)  
  111.     {  
  112.         printf("%d ",a[i]);  
  113.     }  
  114.       
  115.     system("pause");  
  116.     return 0;  
  117. }   
分享到:
评论

相关推荐

    d叉树堆排序,比较好用的堆排序

    标题提到的是“d叉树堆排序”,这是一种基于多分支树结构的排序算法,不同于常见的二叉堆(二叉树结构),它允许每个节点有d个子节点,因此叫做d叉树堆。堆排序是一种比较高效的排序算法,其基本思想是将待排序的...

    堆排序详细图解(通俗易懂)+排序算法-堆排序(超详细)

    堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法...

    VC++-----------堆排序

    堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(最大堆)或小于或等于(最小堆)其子节点的值。堆排序分为...

    堆排序算法源代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。...尽管现代计算机中有更快的排序算法(如快速排序、归并排序等),但堆排序因其简单性和稳定性,仍然是许多程序员的首选工具之一。

    堆排序 里面有关于堆排序的练习台

    2. 应用堆排序对无序数据进行排序,并分析其性能,比如比较平均和最坏情况下的时间效率。 数据输入与输出: 输入数据由多组整数构成,每组数据的个数在输入时给出,最后一组数据以0结束。例如,输入"8"表示接下来有...

    数据结构排序 堆排序

    数据结构排序 堆排序 堆排序是一种常用的排序算法,它使用大堆进行排序。下面是堆排序的详细知识点说明: 堆排序定义 堆排序是一种比较排序算法,它使用大堆(max heap)来对数组进行排序。堆排序的时间复杂度为O...

    堆排序算法实现堆排序

    堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆结构来实现数据的排序。在此,我们将深入探讨堆排序的基本概念、原理以及如何通过编程实现。 一、堆排序的概念 堆是一个近似完全二叉树的结构,...

    C++实现堆排序

    1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。

    算法设计实验报告堆排序代码

    堆排序的主要任务是将无序的序列通过构建堆这一数据结构,然后逐步调整堆,使其满足最大堆或最小堆的特性,最终通过交换堆顶元素与最后一个元素并删除堆顶元素来完成排序。 二、算法设计 堆排序通常分为两个主要...

    堆排序的c++实现代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...

    堆排序算法实现

    本篇文章将基于《算法导论》第六章的内容,深入探讨堆排序的实现原理,并通过具体的C语言代码示例来展示其实现过程。 #### 二、堆排序基础概念 1. **二叉堆**:二叉堆是一种特殊的完全二叉树结构,分为最大堆和...

    多线程排序---希尔排序、快速排序、堆排序

    在计算机科学中,排序是数据处理的一个重要环节,尤其是在大数据处理和数据分析中。多线程技术则能够有效地利用现代多核处理器的计算能力,提高程序的执行效率。本主题主要探讨了三种经典的排序算法——希尔排序、...

    算法导论课后习题与思考题答案

    #### 第6章:堆排序 - **主题概述**:介绍了堆数据结构以及基于此实现的堆排序算法。 - **核心知识点**: - 堆数据结构的定义及其性质。 - 堆排序算法的设计与实现。 - **习题解析**: - 习题6-1:可能要求学生...

    堆排序总结 堆排序总结

    此外,除了二叉堆(Binary Heap),还可以定义 k 叉堆等其他类型的堆。 #### 3. 堆排序的特点 堆排序是一种高效的内部排序算法,其主要特点是: - 将待排序序列看作一棵完全二叉树的顺序存储形式。 - 在排序过程中,...

    堆排序 c语言 演示

    ### 堆排序C语言实现解析 ...通过以上分析可以看出,堆排序算法在C语言中的实现并不复杂,但其效率较高,在实际应用中有广泛的用途。此外,该段代码的可视化输出功能也增强了其实用性和教学价值。

    堆排序算法分析及源代码

    堆排序是一种基于比较的排序算法,它通过构造一个完全二叉树(称为“堆”)来实现排序。在计算机科学中,堆是一个可以被看作是完全二叉树的数组对象,具有以下特性:每个父节点的值都大于或等于其子节点的值,这样的...

    ACM准备模板——堆排序模板

    在ACM(国际大学生程序设计竞赛)中,堆...总之,堆排序是ACM竞赛中不可或缺的工具之一,理解和掌握堆排序及其模板,能够提升你在竞赛中的竞争力。通过不断练习和应用,你将能够灵活运用堆排序解决各种复杂的排序问题。

    堆排序源代码

    ### 堆排序原理与实现 #### 一、堆排序简介 堆排序是一种基于比较的排序算法,利用...通过对提供的源代码的分析,我们不仅了解了堆排序的基本原理,还掌握了其实现细节,这对于进一步学习和掌握排序算法具有重要意义。

    堆排序算法详细配图讲解

    然后对剩下的无序区进行调整,使之重新成为堆。 3. 重复步骤2,直到堆中只剩下一个元素,排序完成。 在堆排序的过程中,堆调整(heapify)操作是核心部分,它负责维持堆的性质。以大根堆为例,这个操作是自底向上...

    数据结构课程设计 实验报告——堆排序

    堆排序的基本思想是先将待排序的序列构造成一个大根堆(或小根堆),然后将堆顶元素与末尾元素交换,减少堆的大小,并对剩余的部分再次调整为大根堆(或小根堆)。通过重复这一过程,可以逐步得到排序后的序列。 ##...

Global site tag (gtag.js) - Google Analytics