算法导论Problem6-3 Youngtableau问题 堆排序应用
这道题大概就是要实现一个数组,这个数组中行所有元素都有序,列所有元素都有序。其实这也是应用堆排序的思想,就是把这个数组的看做是二叉树组成的。一个元素的下面一行的对应一个元素是它的左孩子,右边一个元素是它的右孩子。
这样就可以应用堆排序来解决这个问题了。
同时也是像堆排序一样,实际使用一维数组存储数据,人为规定(按照堆排序的规则,这个是关键思维)地构造二维数组来存储二叉树。
详细程序如下:
#include<iostream> #include<vector> using namespace std; int gChildren = 2; int column = 4; //实际用以为数组表示数据,但是通过人为地规定,构造了一个二维数组,同理可以很轻松地构造三维数组 //主要不同之处就是寻找孩子和父母节点不一样了 int youngTableauUpParent(int cIndex) //cIndex 为C下标0开始 { return cIndex-column; } int youngTableauleftParent(int cIndex) { return cIndex-1; } int youngTableauChild(int cIndex, int leftOrRight) //cIndex 为C下标0开始 { if(leftOrRight==1)//代表左孩子 return cIndex+column; else //代表是右孩子 return cIndex+1; } //找出当前节点和其孩子们的当中的最大值; //本人觉得是本人创造的非常妙的从youngTableauify函数中分离出来的功能函数。极大的简化了对本算法的理解。 template<typename T> int youngTableauMax(vector<T>& youngTableau, int cIndex, int youngTableauSize) { T tempMax = youngTableau[cIndex]; int childIndex = 0; int tempIndex = cIndex; //不同处:如果是最右一列就没有右孩子,如果是最下面一行就没有左孩子,就直接跳过 if(youngTableauChild(cIndex, 1)<youngTableauSize) { childIndex = youngTableauChild(cIndex, 1);//1代表左孩子 if(youngTableau[childIndex]>tempMax) { tempMax = youngTableau[childIndex]; tempIndex = childIndex; } } //注意:少了第二个判断条件会出现错误结果,而且很难Debug。千万不能漏了条件 if((cIndex+1)%column!=0 && (cIndex+1)<youngTableauSize) { childIndex = youngTableauChild(cIndex, 2);//2代表右孩子 if(youngTableau[childIndex]>tempMax) { tempMax = youngTableau[childIndex]; tempIndex = childIndex; } } return tempIndex; } //与堆排序一模一样 //We assume cIndex's children have all been youngTableauified, which is the key to make this algorithm work!!! //比之前的二叉树堆排序更加简洁明了点 template<typename T> void youngTableauify(vector<T>& youngTableau, int cIndex, int youngTableauSize) { if(cIndex<youngTableauSize) { int tempIndex = youngTableauMax(youngTableau, cIndex, youngTableauSize); if(tempIndex != cIndex) { swap(youngTableau[cIndex], youngTableau[tempIndex]); youngTableauify(youngTableau, tempIndex, youngTableauSize); } } } template<typename T> void buildMaxyoungTableau(vector<T>& youngTableau) { for(int i=(youngTableau.size()-1); i>=0; i--) //不同处:从下表倒数第二个开始 youngTableauify(youngTableau, i, youngTableau.size()); } //与堆排序一模一样 template<typename T> void youngTableauSort(vector<T>& youngTableau) { buildMaxyoungTableau(youngTableau); for(int i=youngTableau.size()-1; i>0; i--) { swap(youngTableau[0], youngTableau[i]); youngTableauify(youngTableau, 0, i); } } template<typename T> void youngTableauPrint(const vector<T>& youngTableau) { int i = 1; for(auto x:youngTableau) { cout<<x<<"\t"; if(i%column==0) cout<<endl; i++; //输出格式化的数组,方便检查 } cout<<endl; } void test() { //初始化数组 int a[15] = {2,4,7,1,4,8,9,31,83,28,48,94,87,16,36}; vector<int> youngTableau(a, a+15); //序列输出 cout<<"Befor build youngTableau:\n"; youngTableauPrint(youngTableau); //建立大顶堆后输出 cout<<"After build youngTableau:\n"; buildMaxyoungTableau(youngTableau); youngTableauPrint(youngTableau); //排序后 cout<<"After sort:\n"; youngTableauSort(youngTableau); youngTableauPrint(youngTableau); } int main() { test(); return 0; }
结果:
可以改变column,以改变列数,来看看结果如何,而且最后一行可以是不满列,列如本例中column等于4的时候:
column = 3:
column = 4:
可以是任意列数,甚至可以是column=1,column=100,会有有趣的结果哦,呵呵。有兴趣的可以试一试,想想为什么。
补充:软件开发 , C++ ,