堆排序的改进----多叉堆，C语言实现

系统管理员 2023-03-02 10:51 254阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]多叉堆和二叉堆的相同点和不同点：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]

下面我们对不同的m (子节点个数) 和n (待排序的元素个数) 进行画图 (用Python画图)。从下图我们可以清晰的看到: 当数据量n很小时，不论m是多少，sum的值都差不多，且增长很快。当n ≥ 10000时，sum的增长变得非常缓慢。而这时不同的m之间有较大差别。m为3或4时sum非常接近，当m = 4时sum有最小值。当m ≥ 4时，随着m的增大，sum逐渐增大，当m = 8时，效率与m = 2时相同 (两条曲线完全重合)。从这个图我们得到的结论是：四叉堆的效率最高。四叉堆的效率比二叉堆高20%。当数据量较小时，无论是m是多少，执行效率都差不多。当数据量很大时，才能体现出较大的差距。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 3]  
注：这里分析的是堆的效率，而不是堆排序的效率。其中四叉堆的效率最高。这些堆都可以用于堆排序，也可以用于其它算法。

下面我们就利用m叉堆实现堆排序算法。m叉堆与二叉堆的代码非常相似：

#include <stdio.h> 
    #include <stdlib.h>
    #include <time.h>
    
    int size = 0;
    int arr[10000000]; //对5000000个数据进行排序 
    int sonNum = 3; //子结点个数，4的时候效率最高 
    
    int getRandom(int m) //获得一个随机数
    {
        
    	return rand()%m; //把随机数控制在0~m-1之间
    }
    
    int swap(int a, int b)
    {
        
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    //参数是father的index。根据指定的sonNum个子节点进行计算每个子节点的下标
    int getMaxIndex(int father)
    {
        
    	int maxIndex = father; //默认father是最大值的编号
    	int sonIndex = 0;
    	
    	//计算father及它的sonNum个子节点之间的最大值的编号 
    	for(int i = 0; i < sonNum; i++) //遍历sonNum个子节点 
    	{
        
    		sonIndex = father * sonNum + i; //根据父节点的index，计算子节点的index 
    		if(sonIndex < size && arr[maxIndex] < arr[sonIndex])
    		{
        
    			maxIndex = sonIndex; //更新最大结点的index 
    		}	
    	}
    	return maxIndex; //返回最大值的编号 
    }
    
    //向下调整。i是父节点的编号  
    void shiftDown(int i)
    {
        
    	int maxIndex = 0; 
    	while(true)
    	{
        
    		maxIndex = getMaxIndex(i); //找到father、sonNum个儿子中的最大值
    	
    		//如果father不是最大的值 (也就是说不符合堆的定义)，需要要调整
    		//就是把编号为maxIndex的那个值与father进行交换  
    		if(maxIndex != i)
    		{
        
    			swap(maxIndex, i); //交换  
    			i = maxIndex; //更新i的编号，继续下一轮循环 
    		}
    		else //符合堆的定义时，退出循环 
    		{
        
    			break;
    		}
    	}
    }
    
    //建立大顶堆
    void createMaxHeap()
    {
        
    	//最后一个有子节点的元素的编号是 (n - 1) / sonNum，从它开始调整
    	for(int i = (size - 1) / sonNum; i >= 0; i--)
    	{
        
    		shiftDown(i);
    	}
    } 
    
    void heapSort()
    {
        
    	createMaxHeap(); //建堆 
    	printf("建堆结束\r\n");
    	
    	int size2 = size; //备份size 
    	while(size > 0) //排序
    	{
        
    		//交换堆顶元素与最后一个元素。也就是把最大的元素放到最后 
    		swap(size - 1, 0); 
    		size--; //先n--，然后调整堆 
    		shiftDown(0); //堆顶元素被交换掉了。所以要从顶上开始调整堆 
    	}
    	size = size2; //恢复size
    }
    
    int main()
    {
        
    	size = sizeof(arr) / sizeof(int); //计算数组中有多少个元素 
    	printf("size = %d\r\n", size);
    	
    	for(int i = 0; i < size; i++)
    	{
        
    		arr[i] = getRandom(10000); //随机设置arr中的数据 
    	}
    	
    	time_t t1, t2; //分别声明两种使用方式的赋值对象
        t1 = time(0);
    	heapSort(); //堆排序 
    	t2 = time(0);
    	
    	printf("%d叉堆排序消耗时间: %d\r\n", sonNum, t2 - t1);
    	return 0;
    }

二叉堆和四叉堆的性能对比：![在这里插入图片描述][20200729091136841.png]注：1、测试环境为：Intel I7 4核CPU，16 G内存；Win7，64位系统，Dev C++环境。  
2、数据来源：随机生成的整数，数据范围：1~10000。

测试结果：  
100万个数据进行排序时，四叉堆消耗的时间比二叉堆少25%，但两者仅仅相差1秒钟。当数据量增加到5000万时，四叉堆消耗的时间比二叉堆少44%。

结论：四叉堆的理论性能比二叉堆高20%，但是在较小规模的数据量时，两者区别不大。当数据量非常大 (＞100万个数据) 时，四叉堆才能体现出比较明显的优势。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230208/bc0ffde481be4bb787d3a5f5e8468a02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200729091028818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]: /images/20230208/68ebc51b2f0b4b7b864dcd10c31d95b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 3]: /images/20230208/2992f47cbc7f4401a126f468231f049a.png
[20200729091136841.png]: /images/20230208/b342396b0c7b479e8f02072db19924cd.png