之前实现了堆排序,那是构造二叉树来实现堆排序的,但是其实二叉树还可以用大于等于二叉树来实现的,就是例如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叉树”,会出现比较有趣的现象哦,最终的排序结构也是正确的,有兴趣的朋友试一试。
分享到:
相关推荐
改进的M-ary支持向量机模型及其在模拟电路故障诊断中的应用,王文,李志华,把M-ary支持向量机算法引入到模拟电路的故障诊断中来,提出一种改进M-ary支持向量机算法,利用模糊隶属度去除噪声和孤立点,消除他��
基于正交循环码的M-ary扩频解扩新算法及FPGA实现.pdf
用于 Haxe 的 D-ary 堆实现 Haxe 的通用 arity 堆。 重写了之前关于。
使用 AWGN 信道的不同 M-ary QAM 的 BER 比较。
simulation of M-ary phase shift keying
Simulation of M-Ary FSK with bit rate probability
针对M-ary支持向量机(SVM)多类分类算法结构简单,但泛化能力较弱的特点,提出了与纠错编码理论相结合的改进的M-ary SVM算法。首先,将原始类别信息编码作为信息码;然后结合纠错编码理论及期望的纠错能力,产生一定...
The M-ary support vector machine (SVM) is introduced as a nonparameter nonlinear phase noise (NLPN) mitigation approach for the coherent optical systems. The NLPN tolerance of the system can be ...
k-Ary Search on Modern ProcessorsBenjamin Schlegel Technische Universität Dresdenbenjamin.schlegel@tu- dresden.deRainer Gemulla IBM Almaden Research Centerrgemull@us.ibm.comWolfgang Lehner Technische...
C++ tree 库
FSK调制解调MATLAB源代码 TXT文件中即为matlab的m文件
matlab代码Preference-modeling-with-TOPSIS-using-N-ary-norm-operators 在此版本中,可以找到 n 元 TOPSIS 的 matlab 代码,该代码使用 n 元范数运算符根据实际问题设置对正理想解或负理想解的偏好。 基本 TOPSIS ...
多路堆 algs4 启发使用多路堆(通常称为d- ary 堆)实现的优先级队列: 四个类构成了这个项目的核心: 最大和最小方向,与优先级队列的传统一样。 完全通用的版本…… 在 Kevin Wayne 的建议下,我还添加了一个索引...
对于抽取因子$ d = rac {(p ^ {m} +1)^ 2} {2(p ^ e + 1)} $, 个 序列$ {tr_1 ^ n(alpha ^ i)} $及其抽取序列$ {tr_1 ^ n(alpha ^ {di})} $。 完全确定了相关函数的值分布。 本文的结果概括了Choi,Luo和...
D-Ary布谷鸟过滤器:用于集合成员资格查找的节省空间的数据结构
#资源达人分享计划#
一个完整的k-ary树的实现。 它以广播者节点开始,第一个侦听器节点直接连接到广播者。 新的侦听器节点将连接到广播器,直到侦听器的数量达到 k,然后广播器节点将被视为已满。 然后,尝试连接的下一个侦听器将被...
M阶调制信道的近似信道容量公式,李卫东,杨鸿文,随着高效编码技术的发展,物理层的传输已经可以接近信道容量。在这个情况下,信道容量的分析成为通信系统研究过程中的非常重要参
我们解决了q元完美量子码的分类问题。 我们证明唯一的非平凡q元完美量子码是具有参数(((q(21)-1)/(q(2)-1),q(n-21),3))(q)的那些。 没有其他非平凡的q元完美量子码。
A new two-stage carrier-phase recovery scheme using a combination of an optical pilot-aided algorithm with the crossed constellation transformation algorithm for either square-framed or non-square-...