d-ary heaps 多叉树堆排序C++实现


		之前实现了堆排序，那是构造二叉树来实现堆排序的，但是其实二叉树还可以用大于等于二叉树来实现的，就是例如3叉树每个节点有三个孩子，4叉树，每个节点有四个孩子，等等。
这个是算法导论的一道Problem，其实该注意的地方和堆排序是一样的，所以有了二叉树堆排序的基础之后就很好实现多叉树了。
下面是C++程序：
[cpp]  
#include<iostream>  
#include<vector>  
  
using namespace std;  
  
int gDary = 5;  
//全局函数指定多少分叉树，这里是5，代表5叉树。  
int heapDaryParent(int cIndex)  //cIndex 为C下标0开始  
{  
    return (cIndex-1)/gDary;  
}  
  
int heapDaryChild(int cIndex, int d)    //cIndex 为C下标0开始，d为第几个孩子从1开始  
{  
    return cIndex*gDary+d;  
}  
  
//找出当前节点和其孩子们的当中的最大值;  
//本人觉得是本人创造的非常妙的从daryHeapify函数中分离出来的功能函数。极大的简化了对本算法的理解。  
template<typename T>  
int daryMax(vector<T>& heap, int cIndex, int heapSize)  
{  
    T tempMax = heap[cIndex];  
    int childIndex = 0;  
    int tempIndex = cIndex;  
    for(int i = 1; i<=gDary; i++)  
    {  
        childIndex = heapDaryChild(cIndex, i);  
        if(childIndex<heapSize)  
        {  
            if(heap[childIndex]>tempMax)  
            {  
                tempMax = heap[childIndex];  
                tempIndex = childIndex;  
            }  
        }  
    }  
    return tempIndex;  
}  
  
//We assume cIndex's children have all been heapified, which is the key to make this algorithm work!!!  
//比之前的二叉树堆排序更加简洁明了点  
template<typename T>  
void daryHeapify(vector<T>& heap, int cIndex, int heapSize)  
{  
    if(cIndex<heapSize)  
    {  
        int tempIndex = daryMax(heap, cIndex, heapSize);  
        if(tempIndex != cIndex)  
        {  
            swap(heap[cIndex], heap[tempIndex]);  
            daryHeapify(heap, tempIndex, heapSize);   
        }  
    }  
}  
  
template<typename T>  
void buildMaxDaryHeap(vector<T>& heap)  
{  
    for(int i=(heap.size()-1)/gDary; i>=0; i--)  
        daryHeapify(heap, i, heap.size());  
}  
  
template<typename T>  
void daryHeapSort(vector<T>& heap)  
{  
    buildMaxDaryHeap(heap);  
    for(int i=heap.size()-1; i>0; i--)  
    {  
        swap(heap[0], heap[i]);  
        daryHeapify(heap, 0, i);  
    }  
}  
  
template<typename T>  
void heapPrint(const vector<T>& heap)  
{  
    for(auto x:heap)  
    {  
        cout<<x<<" ";  
    }  
    cout<<endl;  
}  
  
  
void test()  
{  
    //初始化数组  
    int a[15] = {2,4,7,1,4,8,9,31,83,28,48,94,87,16,36};  
    vector<int> heap(a, a+15);  
  
    //序列输出  
    cout<<"Befor build heap:\n";  
    heapPrint(heap);  
  
    //建立大顶堆后输出  
    buildMaxDaryHeap(heap);  
    cout<<"After build heap:\n";  
    heapPrint(heap);  
  
    //排序后  
    cout<<"After sort:\n";  
    daryHeapSort(heap);  
    heapPrint(heap);  
}  
  
int main()  
{  
    test();  
    return 0;  
}  
 
可以修改全局函数gDary=2，或3，或4等，看看结果如何变化：
gDary=2二叉树

三叉树：

四叉树：

五叉树：

可以看出构造的树都不一样的，但是最终的排序结构都正确的。
甚至可以设置gDary为1，为100，成为“1叉树”“100叉树”，会出现比较有趣的现象哦，最终的排序结构也是正确的，有兴趣的朋友试一试。

补充：软件开发 , C++ ,