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

之前实现了堆排序，那是构造二叉树来实现堆排序的，但是其实二叉树还可以用大于等于二叉树来实现的，就是例如3叉树每个节点有三个孩子，4叉树，每个节点有四个孩子，等等。

这个是算法导论的一道Problem，其实该注意的地方和堆排序是一样的，所以有了二叉树堆排序的基础之后就很好实现多叉树了。

下面是C++程序：

#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叉树”，会出现比较有趣的现象哦，最终的排序结构也是正确的，有兴趣的朋友试一试。