您的位置: 首页  >  IT文章  >  第六章堆排序之“对d叉堆的分析”（思考题六-2）

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

分类: IT文章 • 2024-09-20 21:28:43
第六章堆排序之“对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为底哦。（只是和父节点相比，即只进行纵向运动）

 

[cpp] view plaincopy
  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. }   

相关推荐