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++ ,
